- lintcode: (31) 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.
If nums = [3,2,2,1]
and k=2
, a valid answer is 1
.
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
Can you partition the array in-place and in O(n)?
容易想到的一个办法是自左向右遍历,使用right
保存大于等于 k 的索引,i
则为当前遍历元素的索引,总是保持i >= right
, 那么最后返回的right
即为所求。
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) {
if (i != right) {
int temp = nums[i];
nums[i] = nums[right];
nums[right] = temp;
}
++right;
}
}
return right;
}
};
自左向右遍历,遇到小于 k 的元素时即和right
索引处元素交换,并自增right
指向下一个元素,这样就能保证right
之前的元素一定小于 k.
遍历一次数组,时间复杂度最少为
有了解过 Quick Sort 的做这道题自然是分分钟的事,使用左右两根指针
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;
}
};
大循环能正常进行的条件为 while
循环时务必进行越界检查!
找到不满足条件的索引时即交换其值,并递增left
, 递减right
. 紧接着进行下一次循环。最后返回left
即可,当nums
为空时包含在left = 0
之中,不必单独特殊考虑,所以应返回left
而不是right
.
只需要对整个数组遍历一次,时间复杂度为