解
第一步，万年不变的查错。如果给的array是null或空，直接return 0
public int partitionArray(int[] nums, int k) {
if(nums == null || nums.length == 0) {
return 0;
}
...
}
这道题很简单，简直对不起medium难度。分明就是quickSort的第一步嘛。总的来说，就是左右两个pointer，左边如果碰到大于等于k的，右边如果碰到小于k的，那么就左右互换。最后return那个，可能需要想一下，要求nums[index]必须大于等于k。这个while loop的结束条件就是左边超过右边，所以其实左边比右边大，所以最后要return left;
直接上完整的code了，没有难度。
public class Solution {
/*
* @param nums: The integer array you should partition
* @param k: An integer
* @return: The index after partition
*/
public int partitionArray(int[] nums, int k) {
if(nums == null || nums.length == 0) {
return 0;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
while (left <= right && nums[left] < k) {
left++;
}
while (left <= right && nums[right] >= k) {
right --;
}
if (left <= right) {
swap(nums, left, right);
}
}
return left;
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
分析
时间复杂度
只遍历了一次，所以O(n)。
空间复杂度
O(1)。
总的来说，太简单了。更简单的一种方法其实是一次遍历，数比k小的数字有几个，然后返回。如果真的面试碰到的话，应该不要傻傻的直接two pointer。应该先说最明显也是最简单的答案，然后等人家followup。
