leetcode-75. 颜色分类

JAVA解法

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]，过程如表格所示：

i = 0

2	0	2	1	1	0
p0，p1，i

此时 i 所在位置的数为 2 无需任何操作。

i = 1

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

i = 2

0	2	2	1	1	0
	p0，p1	i

此时 i 所在位置的数为 2 无需任何操作。

i = 3

0	2	2	1	1	0
	p0，p1		i

此时 i 所在位置的数为 1 ，则与 p1 进行交换，结果如下：

0	1	2	2	1	0
	p0	p1	i

在这里可以推一下，假如上边遇到 0 没有同时维护两个指针的话，这里就乱了，即使往后也没办法纠正，最后有个 1 位置错了，这就是为什么遇到 0 要同时维护两个指针的原因了。

i = 4

0	1	2	2	1	0
	p0	p1		i

此时 i 所在位置的数为 1 ，则与 p1 进行交换，结果如下：

0	1	1	2	2	0
	p0		p1	i

i = 5

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. 颜色分类