class Solution {
public void sortColors(int[] nums) {
// 获取数组长度
int n = nums.length;
// 定义两个指针的位置
int p0 = 0, p1 = 0;
// 开始遍历
for (int i = 0; i < n; ++i) {
// 当找到数字 1 时
if (nums[i] == 1) {
// 把 1 换到 p1 的位置
int temp = nums[i];
nums[i] = nums[p1];
nums[p1] = temp;
// 维护 p1
++p1;
// 当找到数字 0 时
} else if (nums[i] == 0) {
// 把 0 换到 p0 的位置
int temp = nums[i];
nums[i] = nums[p0];
nums[p0] = temp;
// 若 p0 < p1 还得将此时 i 的位置与 p1 位置交换
if (p0 < p1) {
temp = nums[i];
nums[i] = nums[p1];
nums[p1] = temp;
}
// 同时维护 p0 和 p1
++p0;
++p1;
}
}
}
}
这道题是「荷兰国旗问题」的典型题目,由计算机科学家 Edsger Wybe Dijkstra 首先提出。
用一次遍历的话需要两个指针,先获取数组长度,定义两个指针 p0 和 p1 都指向第一个数,p0 是用来当找到 0 时进行交换的位置标记,同时维护 p0 和 p1 指针,同理 p1 则是用来当找到 1 时交换位置的标记,同时维护 p1 指针(疑惑:为什么这里 遇到 0 要维护两个指针,而遇到 1 只维护 p1 一个指针?接着往下看)。用 for 循环遍历数组,当遇到 0 或者 1 时,分别与标记位置进行交换,可用题目示例来举例,题目给的是 nums = [2,0,2,1,1,0]
,过程如表格所示:
2 | 0 | 2 | 1 | 1 | 0 |
---|---|---|---|---|---|
p0,p1,i |
此时 i 所在位置的数为 2 无需任何操作。
2 | 0 | 2 | 1 | 1 | 0 |
---|---|---|---|---|---|
p0,p1 | i |
此时 i 所在位置的数为 0 ,则与 p0 进行交换,同时判断 p0 与 p1 的位置的先后,假如 p0 在 p1 后边的话还得再交换一次,即 i 所在位置的数与 p1 位置所在的数交换,在这里 p0 与 p1 指向的是同一个数,因此不用换,结果如下:
0 | 2 | 2 | 1 | 1 | 0 |
---|---|---|---|---|---|
p1,p0,i |
0 | 2 | 2 | 1 | 1 | 0 |
---|---|---|---|---|---|
p0,p1 | i |
此时 i 所在位置的数为 2 无需任何操作。
0 | 2 | 2 | 1 | 1 | 0 |
---|---|---|---|---|---|
p0,p1 | i |
此时 i 所在位置的数为 1 ,则与 p1 进行交换,结果如下:
0 | 1 | 2 | 2 | 1 | 0 |
---|---|---|---|---|---|
p0 | p1 | i |
在这里可以推一下,假如上边遇到 0 没有同时维护两个指针的话,这里就乱了,即使往后也没办法纠正,最后有个 1 位置错了,这就是为什么遇到 0 要同时维护两个指针的原因了。
0 | 1 | 2 | 2 | 1 | 0 |
---|---|---|---|---|---|
p0 | p1 | i |
此时 i 所在位置的数为 1 ,则与 p1 进行交换,结果如下:
0 | 1 | 1 | 2 | 2 | 0 |
---|---|---|---|---|---|
p0 | p1 | i |
0 | 1 | 1 | 2 | 2 | 0 |
---|---|---|---|---|---|
p0 | p1 | i |
此时 i 所在位置的数为 0 ,则与 p0 进行交换,同时这里满足 p0 在 p1 后边,还得再交换一次,即 i 所在位置的数与 p1 位置所在的数交换,结果如下:
0 | 0 | 1 | 1 | 2 | 2 |
---|---|---|---|---|---|
p0 | p1 | i |
这就是最终的结果了。
leetcode原题:75. 颜色分类