颜色分类

发表于 | 分类于 |
字数统计: 380 字 | 阅读时长 ≈ 1 分钟

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

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

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

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

示例 3：
输入：nums = [0]
输出：[0]

示例 4：
输入：nums = [1]
输出：[1]

方法一：双指针

思想类似于刷漆

以[2 0 2 1 1 1 0]为例 大致可以这样理解：

[2 0 2 1 1 1 0]
-> [2 2 2 2 2 2 2] 先全填上2
-> [1 1 1 1 1 2 2] 统计下0和1的个数之和(作为数字1的右侧边界)，然后填上1
-> [0 0 1 1 1 2 2] 统计下0的个数（作为数字0的右侧边界），然后填上0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void sortColors(int[] nums) {
        int n0 = 0, n1 = 0;
        for(int i = 0; i < nums.length; i++) {
            int temp = nums[i];
            nums[i] = 2;
            if(temp <= 1) {
                nums[n1++] = 1;
            } 
            if(temp == 0) {
                nums[n0++] = 0;
            }
        }
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。
  • 空间复杂度：O(1)。

执行结果：通过

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：36.8 MB, 在所有 Java 提交中击败了77.67%的用户