image.png
https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/72953
解法一：** 自左向右**
容易想到的一个办法是自左向右遍历，使用right保存大于等于 k 的索引，i则为当前遍历元素的索引，总是保持i >= right, 那么最后返回的right即为所求。
class Solution {
public:
/**
* @param nums: The integer array you should partition
* @param k: An integer
* @return: The index after partition
*/
int partitionArray(vector<int> &nums, int k) {
// write your code here
int right = 0;
for(int i = 0; i < nums.size(); i++){
if(nums[i] < k && i >= right){
int tmp = nums[i];
nums[i] = nums[right];
nums[right] = tmp;
right++;
}
}
return right;
}
}
解法二：两根指针，类似于快速排序
class Solution {
public:
/**
* @param nums: The integer array you should partition
* @param k: An integer
* @return: The index after partition
*/
int partitionArray(vector<int> &nums, int k) {
// write your code here
int left = 0;
int right = nums.size() - 1;
while(left <= right){
while(nums[right] >= k && right >= left){
right--;
}
while(nums[left] < k && right >= left){
left++;
}
if(left < right){
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
}
return right+1;
}
};
