75. 颜色分类

刷题记录
留言

75. 颜色分类

题目

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

1
2
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

1
2
输入：nums = [2,0,1]
输出：[0,1,2]

示例 3：

1
2
输入：nums = [0]
输出：[0]

示例 4：

1
2
输入：nums = [1]
输出：[1]

提示：

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

进阶：

  • 你可以不使用代码库中的排序函数来解决这道题吗？
  • 你能想出一个仅使用常数空间的一趟扫描算法吗？

注意要点

题目要求有原地排序、禁止使用排序函数以及常数空间一边扫描等要求。所以我们可以排除sort函数、hash、新数组等方法。而一边扫描最常用的就是双指针或多指针。

这道题是“荷兰国旗问题”。又是Dijkstra提的。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        // p0用来交换0 p1用来交换1
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            // 如果遍历到的数为1
            if (nums[i] == 1) {
                // 和p1交换，p1++
                swap(nums[i], nums[p1]);
                ++p1;
                // 如果遍历到的数为0
            } else if (nums[i] == 0) {
                // 交换p0
                swap(nums[i], nums[p0]);
                // 如果此时p0在p1前面，说明此时1被交换到了外面，所以需要再交换到p1的位置
                if (p0 < p1) {
                    swap(nums[i], nums[p1]);
                }
                // 都要自增
                ++p0;
                // 如果p0<p1,因为做了交换，所以要自增
                // 如果p1<=p0。显然该位置放了0 所以p1也要自增
                ++p1;
            }
        }
    }
};