描述
将一个没有经过排序的整数数组划分为 3 部分:
1.第一部分中所有的值都 < low
2.第二部分中所有的值都 >= low并且 <= high
3.第三部分中所有的值都 > high
返回任意一种可能的情况。
注意事项
在所有测试数组中都有 low <= high。
样例
给出数组
[4,3,4,1,2,3,1,2]，low =2，high =3。变为
[1,1,2,3,2,3,4,4]，([1,1,2,2,3,3,4,4] 也是正确答案，但 [1,2,1,2,3,3,4,4] 不是)
1.在原地完成
2.用一个循环完成
注意
只要切分数组不是等于情况也要均分，都无需在while判断中考虑left == right情况，因为压根不会出现
在切分时还要考虑切分参照值是否在数组中存在，如不存在要考虑越界情形
代码
- 两根指针
public class Solution {
/**
* @param nums an integer array
* @param low an integer
* @param high an integer
* @return nothing
*/
public void partition2(int[] nums, int low, int high) {
// Write your code here
if (nums == null || nums.length <= 1) {
return;
}
int pl = 0, pr = nums.length - 1;
int i = 0;
while (i <= pr) {
if (nums[i] < low) {
swap(nums, pl, i);
pl++;
// 只有左边等于 low 时才会跳过，大于 high 时会处理，
// 所以此处交换过来的值只能是 low，不可能大于 low，可以直接 i++
i++;
} else if (nums[i] > high) {
swap(nums, pr, i);
pr--;
} else {
i ++;
}
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
- 切分两次
public class Solution {
/**
* @param nums an integer array
* @param low an integer
* @param high an integer
* @return nothing
*/
public void partition2(int[] nums, int low, int high) {
// Write your code here
int left = 0;
int right = nums.length - 1;
// 首先把区间分为 < low 和 >= low 的两个部分
while(left <= right) {
while(left <= right && nums[left] < low) {
left ++;
}
while(left <= right && nums[right] >= low) {
right --;
}
if(left <= right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left ++;
right --;
}
}
// 上面计算left正好是第一个大于等于low的位置
// 然后从 >= low 的部分里分出 <= high 和 > high 的两个部分
right = nums.length - 1;
while(left <= right) {
while(left <= right && nums[left] <= high) {
left ++;
}
while(left <= right && nums[right] > high) {
right --;
}
if(left <= right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left ++;
right --;
}
}
}
}
