Partition Array – Lintcode Java | Welkin Lan
Given an array
http://www.code123.cc/docs/leetcode-notes/integer_array/partition_array.html
http://www.jiuzhang.com/solutions/partition-array/
Read full article from Partition Array – Lintcode Java | Welkin Lan
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
Example
If nums =
[3,2,2,1] and k=2, a valid answer is 1.
Note
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
If all elements in nums are smaller than k, then return nums.length
Challenge
Partition the array with two pointers. The order needs not to be preserved.
Can you partition the array in-place and in O(n)?
http://www.code123.cc/docs/leetcode-notes/integer_array/partition_array.html
有了解过 Quick Sort 的做这道题自然是分分钟的事，使用左右两根指针 left,right 分别代表小于、大于等于 k 的索引，左右同时开工，直至 left>right.
public int partitionArray(int[] nums, int k) {
//write your code here
if (nums == null || nums.length == 0) {
return 0;
}
int start = 0, end = nums.length - 1;
while (start <= end) {
while (start <= end && nums[start] < k) {
start++;
}
while (start <= end && nums[end] >= k) {
end--;
}
if (start < end) {
int temp = nums[end];
nums[end] = nums[start];
nums[start] = temp;
end--;
start++;
}
}
return start;
}
public int partitionArray(int[] nums, int k) {
//write your code here
if (nums == null || nums.length == 0) {
return 0;
}
int start = 0, end = nums.length - 1;
while (start < end) {
if (nums[start] < k) {
start++;
}
else {
int temp = nums[end];
nums[end] = nums[start];
nums[start] = temp;
end--;
}
}
if (nums[end] < k) {
return end + 1;
}
else {
return end;
}
}
http://www.jiuzhang.com/solutions/partition-array/
Read full article from Partition Array – Lintcode Java | Welkin Lan
