Partition Array详解编程语言

Given an array nums of integers and an int k, partition the array 
(i.e move the elements in "nums") such that: 
 
All elements < k are moved to the left 
All elements >= k are moved to the right 
Return the partitioning index, i.e the first index i nums[i] >= k. 
 
Example 
If nums=[3,2,2,1] and k=2, a valid answer is 1. 
 
Note 
You should do really partition in array nums instead of just 
counting the numbers of integers smaller than k. 
 
If all elements in nums are smaller than k, then return nums.length 
 
Challenge 
Can you partition the array in-place and in O(n)?

class Solution { 
public: 
    int partitionArray(vector<int> &nums, int k) { 
        int right = 0; 
        const int size = nums.size(); 
        for (int i = 0; i < size; ++i) { 
            if (nums[i] < k && i >= right) { 
                int temp = nums[i]; 
                nums[i] = nums[right]; 
                nums[right] = temp; 
                ++right; 
            } 
        } 
 
        return right; 
    } 
};

class Solution { 
public: 
    int partitionArray(vector<int> &nums, int k) { 
        int left = 0, right = nums.size() - 1; 
        while (left <= right) { 
            while (left <= right && nums[left] < k) ++left; 
            while (left <= right && nums[right] >= k) --right; 
            if (left <= right) { 
                int temp = nums[left]; 
                nums[left] = nums[right]; 
                nums[right] = temp; 
                ++left; 
                --right; 
            } 
        } 
 
        return left; 
    } 
};