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.

分析：

这道题目首先看清楚return的是什么，return第一个>=k的index就返回start。

其次，在用while方法的移动start和end时候，有一种corner case，就是说整个数组全都小于k，就有可能把start移动到数组外面去了。这时候要加一个判断，就是start < n，end >= 0。

解法1：

class Solution {
public:
    int partitionArray(vector<int> &nums, int k) {
        // write your code here
        int start = 0;
        int end = nums.size() - 1;
        while (start <= end) {
            while (start < nums.size() && nums[start] < k) {
                start++;
            }
            while (end >= 0 && nums[end] >= k) {
                end--;
            }
            if (start <= end) {
                swap(nums[start], nums[end]);
            }
        }
        return start;
    }
};

解法2：

class Solution {
public:
    int partitionArray(vector<int> &nums, int k) {
        // write your code here
        int start = 0;
        int end = nums.size() - 1;
        while (start <= end) {
            if (nums[start] < k) {
                start++;
            } else {
                swap(nums[start], nums[end]);
                end--;
            }
        }
        return start;
    }
};