Partition Array

http://www.lintcode.com/en/problem/partition-array/

Discussion

这题其实就是Sort Colors问题的简化版，可以认为是两种颜色sort，更简单了。

Solution

class Solution {
public:
    int partitionArray(vector<int> &nums, int k) {
        // write your code here
        int n = nums.size();
        if(n==0) return 0;
        int largeIdx = n-1;
        int i = 0;
        for(i=0; i<largeIdx+1;) {//注意是i<largeIdx+1
            if(nums[i] < k) {
                i++;
            } else {
                swap(nums[i], nums[largeIdx--]);
            }
        }
        //if(nums[i] <k) return n;
        return i;//i左边都是小于k的，所以返回i就可以了，如果所有number都小于k，到这里的时候i已经是n了
    }
};