颜色分类

发表于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

LeetCode每日一题，75. Sort Colors

先看题目描述

给定一个 nums 数组，只包含 0，1 和 2，0 代表红色，1 代表白色，2 代表蓝色，让我们对其进行排序，使得相同的元素相邻，并按照，红色，白色，蓝色进行排列

算法和思路

用计数排序和快排的 partition 均可，但第二种方法可以实现 O(1) 的空间复杂度

计数排序

我们可以先使用迭代计算出0，1 和 2 元素的个数，然后按照 0，1 和 2 的排序，重写当前数组

基于快速排序的 partition

受到快速排序中 partition 过程的启发，我们可以使用三个指针，一个指针 i 用于遍历数组，一个指针 index0 表示 0 和 1 的边界，另一个指针 index1 表示 1 和 2 的边界

初始化 index0 = -1，index1 = -1，i = 0，用指针 i 来遍历 nums 数组：

  • 若 nums[i] = 1，则将 index1 + 1，然后互换 nums[index1] 与 nums[i]
  • 若 nums[i] = 0，则将 index0 与 index1 都加 1，然后互换 nums[index0] 与 nums[i]，若此时 index0 不等于 index1，则说明互换的是 0 和 1，那么还要将 1 换回以前所在的区间，即再将 nums[index1] 与 nums[i] 互换

算法源码

计数排序

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
class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        int num0 = 0;
        int num1 = 0;
        int num2 = 0;
        for (int num: nums) {
            switch (num) {
                case 0: num0++;
                break;
                case 1: num1++;
                break;
                default:num2++;
            }
        }
        int index = 0;
        for (int i = 0; i < num0; i++) {
            nums[index++] = 0;
        }
        for (int i = 0; i < num1; i++) {
            nums[index++] = 1;
        }
        for (int i = 0; i < num2; i++) {
            nums[index++] = 2;
        }
    }
}

快速排序的 partition

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
class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        int index0 = -1;
        int index1 = -1;
        for (int i = 0; i < len; i++) {
            int num = nums[i];
            if (num == 2) continue;
            if (num == 1) {
                index1++;
                swap(nums, i, index1);
            } else if (num == 0) {
                index0++;
                index1++;
                swap(nums, i, index0);
                if (index1 != index0) {
                    swap(nums, i, index1);
                }
            }
        }
    }

    private void swap(int[] nums, int i ,int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}