题目
题目链接
题解
class Solution {
public void sortColors(int[] nums) {
twoPointer(nums);
}
/**
* 统计并重写
* 1.第一次遍历统计0 1 2出现的次数
* 2.第二次遍历依据次数依次将0 1 2覆盖到数组中
*/
private void countAndRewrite(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
// 统计
int c0 = 0, c1 = 0;
for (int e : nums) {
if (e == 0) {
c0++;
} else if (e == 1) {
c1++;
}
}
// 重写
for (int i = 0; i < nums.length; i++) {
if (c0 > 0) {
nums[i] = 0;
c0--;
} else if (c1 > 0) {
nums[i] = 1;
c1--;
} else {
nums[i] = 2;
}
}
}
/**
* 双指针
* 1.nums[0..p0-1]保存0
* 2.nums[p0..p2-1]保存1
* 3.nums[p2..len-1]保存2
*/
private void twoPointer(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int n = nums.length;
int p0 = 0, p1 = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] == 1) {
// 交换1
// 将 i 处数字与 p1 处数字交换
nums[i] = nums[p1];
nums[p1] = 1;
// 存1只需要后移p1指针
++p1;
} else if (nums[i] == 0) {
// 交换0
// 将 i 处数字与 p0 处数字交换
nums[i] = nums[p0];
nums[p0] = 0;
// 如果p0在p1前边，那上一步交换掉的一定是1
if (p0 < p1) {
// 需要再次将1交换到p1处
nums[i] = nums[p1];
nums[p1] = 1;
}
// 存0后两个指针都需要后移
++p0;
++p1;
}
}
}
}