一种元素划分方法

描述

给定一个整数数组nums和一个整数kk表示数组中的一个位置,取值为[0,nums.size()-1]中的一个值,该位置元素即为pivot,在一次遍历中,将元素划分为小于、等于和大于pivot的三组。

Solution

维护四个子数组:bottom(元素小于pivot),middle (元素等于pivot),unclassifiedtop(元素大于pivot)。一开始所有的元素都是unclassified,遍历这个组的元素,根据当前元素与pivot的相对关系将元素移动到bottommiddletop组。

举个具体的例子:假设数组nums[-3,0,-1,1,1,?,?,?,4,2],其中1?分别表示pivot和unclassified元素。对于第一个未分类的元素,nums[5],共有三种可能性:

  • nums[5] < pivot,例如nums[5] = -5。我们将其与第一个1进行交换,得到新数组为[-3,0,-1,-5,1,1,?,?,4,2]

  • nums[5] == pivot,例如nums[5] = 1。我们无需任何移动,只需继续考察下一个未分类的元素,新数组为[-3,0,-1,1,1,1,?,?,4,2]

  • nums[5] > pivot,例如nums[5] = 3。我们将其与未分类的最后一个元素进行交换,得到新数组为[-3,0,-1,1,1,?,?,3,4,2]

C++ 实现

void partition(vector<int>& nums, int k) {
    int pivot = nums[k];
    // invairants:
    // bottom: nums[0, smaller - 1]
    // middle: nums[smaller, equal - 1]
    // unclassified: nums[equal, larger - 1]
    // top: nums[larger, nums.size() - 1]
    int smaller = 0, equal = 0, larger = nums.size();
    // keep iterating as long as there is an unclassified element
    while (equal < larger) {
        if (nums[equal] < pivot) {
            swap(nums[smaller++], nums[equal++]);
        } else if (nums[equal] == pivot) {
            ++equal;
        } else {
            swap(nums[equal], nums[--larger]);
        }
    }
}

每次迭代将未分类元素的数目减1,每次迭代的时间开销是O(1),总的时间复杂度为O(n)。很明显,空间复杂度为O(1)

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s