LeetCode-75. 颜色分类

问题地址

LeetCode每日一题/2020-10-07

LeetCode75. 颜色分类

问题描述

规则

• 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
• 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:

不能使用代码库中的排序函数来解决这道题。

示例

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶

• 一个直观的解决方案是使用计数排序的两趟扫描算法。
• 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
  你能想出一个仅使用常数空间的一趟扫描算法吗？

解析

解题思路

数据操作分析

• 见思路分析

复杂度分析

1. 时间复杂度
2. 空间复杂度

编码实现

官方解法

前言

• 本题是经典的「荷兰国旗问题」，由计算机科学家 Edsger W. Dijkstra 首先提出。
• 根据题目中的提示，我们可以统计出数组中 0,1,2 的个数，再根据它们的数量，重写整个数组。这种方法较为简单，也很容易想到，而本题解中会介绍两种基于指针进行交换的方法。

方法一：单指针

思路与算法

• 我们可以考虑对数组进行两次遍历。在第一次遍历中，我们将数组中所有的 0 交换到数组的头部。在第二次遍历中，我们将数组中所有的 1 交换到头部的 0 之后。此时，所有的 2 都出现在数组的尾部，这样我们就完成了排序。
• 具体地，我们使用一个指针 \textit{ptr} 表示「头部」的范围，\textit{ptr} 中存储了一个整数，表示数组 \textit{nums} 从位置 0 到位置 \textit{ptr}-1 都属于「头部」。\textit{ptr} 的初始值为 0，表示还没有数处于「头部」。
• 在第一次遍历中，我们从左向右遍历整个数组，如果找到了 0，那么就需要将 0 与「头部」位置的元素进行交换，并将「头部」向后扩充一个位置。在遍历结束之后，所有的 0 都被交换到「头部」的范围，并且「头部」只包含 0。
• 在第二次遍历中，我们从「头部」开始，从左向右遍历整个数组，如果找到了 1，那么就需要将 1 与「头部」位置的元素进行交换，并将「头部」向后扩充一个位置。在遍历结束之后，所有的 1 都被交换到「头部」的范围，并且都在 0 之后，此时 2 只出现在「头部」之外的位置，因此排序完成。

复杂度分析：

1. 时间复杂度:O(n)，其中 n 是数组 \textit{nums} 的长度。
2. 空间复杂度：O(1)。

编码实现

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int ptr = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
        for (int i = ptr; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
    }
}

方法二：双指针

思路及算法：

• 方法一需要进行两次遍历，那么我们是否可以仅使用一次遍历呢？我们可以额外使用一个指针，即使用两个指针分别用来交换 0 和 1。
• 具体地，我们用指针 p_0 来交换 0，p_1 来交换 1，初始值都为 0。当我们从左向右遍历整个数组时：
  • 如果找到了 1，那么将其与 \textit{nums}[p_1] 进行交换，并将 p_1 向后移动一个位置，这与方法一是相同的；
  • 如果找到了 0，那么将其与 \textit{nums}[p_0] 进行交换，并将 p_0 向后移动一个位置。这样做是正确的吗？我们可以注意到，因为连续的 0 之后是连续的 1，因此如果我们将 0 与 \textit{nums}[p_0] 进行交换，那么我们可能会把一个 1 交换出去。当 p_0 < p_1 时，我们已经将一些 1 连续地放在头部，此时一定会把一个 1 交换出去，导致答案错误。因此，如果 p_0 < p_1，那么我们需要再将 \textit{nums}[i] 与 \textit{nums}[p_1] 进行交换，其中 i 是当前遍历到的位置，在进行了第一次交换后，\textit{nums}[i] 的值为 1，我们需要将这个 1 放到「头部」的末端。在最后，无论是否有 p_0 < p_1，我们需要将 p_0 和 p_1 均向后移动一个位置，而不是仅将 p_0 向后移动一个位置。

复杂度分析：

1. 时间复杂度:O(n)，其中 n 是数组 \textit{nums} 的长度。
2. 空间复杂度：O(1)。

编码实现

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
                ++p1;
            } else if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                if (p0 < p1) {
                    temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                }
                ++p0;
                ++p1;
            }
        }
    }
}

方法三：双指针

思路及算法：

• 与方法二类似，我们也可以考虑使用指针 p_0 来交换 0，p_2 来交换 2。此时，p_0 的初始值仍然为 0，而 p_2 的初始值为 n-1。在遍历的过程中，我们需要找出所有的 0 交换至数组的头部，并且找出所有的 2 交换至数组的尾部。
• 由于此时其中一个指针 p_2 是从右向左移动的，因此当我们在从左向右遍历整个数组时，如果遍历到的位置超过了 p_2 ，那么就可以直接停止遍历了。
• 具体地，我们从左向右遍历整个数组，设当前遍历到的位置为 i，对应的元素为 \textit{nums}[i]；
  • 如果找到了 0，那么与前面两种方法类似，将其与 \textit{nums}[p_0] 进行交换，并将 p_0 向后移动一个位置；
  • 如果找到了 2，那么将其与 \textit{nums}[p_2] 进行交换，并将 p_2 向前移动一个位置。
• 这样做是正确的吗？可以发现，对于第二种情况，当我们将 \textit{nums}[i] 与\textit{nums}[p_2] 进行交换之后，新的 \textit{nums}[i] 可能仍然是 2，也可能是 0。然而此时我们已经结束了交换，开始遍历下一个元素 \textit{nums}[i+1]，不会再考虑 \textit{nums}[i] 了，这样我们就会得到错误的答案。
• 因此，当我们找到 2 时，我们需要不断地将其与 \textit{nums}[p_2] 进行交换，直到新的 \textit{nums}[i] 不为 2。此时，如果 \textit{nums}[i] 为 0，那么对应着第一种情况；如果 \textit{nums}[i] 为 1，那么就不需要进行任何后续的操作。
  

复杂度分析：

1. 时间复杂度:O(n)，其中 n 是数组 \textit{nums} 的长度。
2. 空间复杂度：O(1)。

编码实现

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i <= p2; ++i) {
            while (i <= p2 && nums[i] == 2) {
                int temp = nums[i];
                nums[i] = nums[p2];
                nums[p2] = temp;
                --p2;
            }
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                ++p0;
            }
        }
    }
}

精彩评论

跳转地址1：快速排序 partition（重点在设计循环不变量）

什么是 partition ？

思路：

• 我们在学习 快速排序 的时候知道，可以选择一个标定元素（称为 pivot ，一般而言随机选择），然后通过一次扫描，把数组分成三个部分：
  • 第 1 部分严格小于 pivot 元素的值；
  • 第 2 部分恰好等于 pivot 元素的值；
  • 第 3 部分严格大于 pivot 元素的值。
• 第 2 部分元素就是排好序以后它们应该在的位置，接下来只需要递归处理第 1 部分和第 3 部分的元素。
• 经过一次扫描把整个数组分成 3 个部分，正好符合当前问题的场景。写对这道题的方法是：把循环不变量的定义作为注释写出来，然后再编码。

复习 partition

• 说明：这部分与本题解法无直接关系，直接跳过不影响后续内容的阅读。
• 下面的动画，从一个中间的状态开始演示，通过循环变量 i 以及设置两个边界变量 lt 和 gt 把一个数组分成 3 个部分。
  

• 以下给出不同的写法，循环不变量的定义写在了注释中。使用「循环不变量」编码是为了便于我们处理细节，也方便他人阅读代码。

编码实现

循环不变量定义 1

• 循环不变量：声明的变量在遍历的过程中需要保持定义不变。

• 设计循环不变量的原则

  • 说明：设计循环不变量的原则是 不重不漏。
    • len 是数组的长度；
    • 变量 zero 是前两个子区间的分界点，一个是闭区间，另一个就必须是开区间；
    • 变量 i 是循环变量，一般设置为开区间，表示 i 之前的元素是遍历过的；
    • two 是另一个分界线，我设计成闭区间。
• 如果循环不变量定义如下：
  • 所有在子区间 [0, zero) 的元素都等于 0；
  • 所有在子区间 [zero, i) 的元素都等于 1；
  • 所有在子区间 [two, len – 1] 的元素都等于 2。
• 于是编码要解决以下三个问题：
  • 变量初始化应该如何定义；
  • 在遍历的时候，是先加减还是先交换；
  • 什么时候循环终止。
• 处理这三个问题，完全看循环不变量的定义。
  • 编码的时候，zero 和 two 初始化的值就应该保证上面的三个子区间全为空；
  • 在遍历的过程中，「下标先加减再交换」、还是「先交换再加减」就看初始化的时候变量在哪里；
  • 退出循环的条件也看上面定义的循环不变量，在 i == two 成立的时候，上面的三个子区间就正好 不重不漏 地覆盖了整个数组，并且给出的性质成立，题目的任务也就完成了。

• 代码如下：

import java.util.Arrays;
public class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return;
        }
        // all in [0, zero) = 0
        // all in [zero, i) = 1
        // all in [two, len - 1] = 2

        // 循环终止条件是 i == two，那么循环可以继续的条件是 i < two
        // 为了保证初始化的时候 [0, zero) 为空，设置 zero = 0，
        // 所以下面遍历到 0 的时候，先交换，再加
        int zero = 0;

        // 为了保证初始化的时候 [two, len - 1] 为空，设置 two = len
        // 所以下面遍历到 2 的时候，先减，再交换
        int two = len;
        int i = 0;
        // 当 i == two 上面的三个子区间正好覆盖了全部数组
        // 因此，循环可以继续的条件是 i < two
        while (i < two) {
            if (nums[i] == 0) {
                swap(nums, i, zero);
                zero++;
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                two--;
                swap(nums, i, two);
            }
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

• 复杂度分析：
  • 时间复杂度：O(N)，这里 N 是输入数组的长度；
  • 空间复杂度：O(1)。

循环不变量定义 2

• 代码如下：

public class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return;
        }
        // all in [0, zero] = 0
        // all in (zero, i) = 1
        // all in (two, len - 1] = 2

        // 为了保证初始化的时候 [0, zero] 为空，设置 zero = -1，
        // 所以下面遍历到 0 的时候，先加，再交换
        int zero = -1;

        // 为了保证初始化的时候 (two, len - 1] 为空，设置 two = len - 1
        // 所以下面遍历到 2 的时候，先交换，再减
        int two = len - 1;
        int i = 0;
        // 当 i == two 的时候，还有一个元素还没有看，
        // 因此，循环可以继续的条件是 i <= two
        while (i <= two) {
            if (nums[i] == 0) {
                zero++;
                swap(nums, i, zero);
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                swap(nums, i, two);
                two--;
            }
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

• 复杂度分析：
  • 时间复杂度：O(N)，这里 N 是输入数组的长度；
  • 空间复杂度：O(1)。

体会

• 说明：这种做法是我在 Java 的 JDK 的源码中 Arrays.sort() 中学到的。
• 我的体会是：
  • 编码者应该在代码中使用注释表达这段代码编写的算法思想，提醒自己也方便他人。
  • 但是源代码中类似 ++k = a[left – 1] 这样的代码建议不要写，会给阅读者带来理解上的障碍，这种做法也是《阿里巴巴 Java 开发手册》中不推荐的，理由是：变量的值发生变化是一个很重要的逻辑，应该单独成为一行，否则不利于调试和以后定位问题，这种语法糖我个人认为应该禁止使用。
    

相关问题

• 下面这两个问题可以用于复习 partition 的过程。
  • 「力扣」第 215 题：数组中的第 K 个最大元素（中等）
  • 「力扣」第 451 题：根据字符出现频率排序（中等）

• 说明：这一题参与比较的是字符，题目中虽然没有给出字符的范围，但是通过测试可以知道，测试数据的字符不超过 128 个，符合有大量重复元素出现的情况，可以使用 partition 的过程对输入数据进行排序。

• 「力扣」第 451 题参考代码：手写快速排序，如果很熟悉 partition，代码只需要稍作修改即可。

import java.util.Random;
public class Solution {
    private int[] freq;
    private static final Random RANDOM = new Random();
    public String frequencySort(String s) {
        // 先转换为字符数组，以避免 charAt() 方法每次都检查下标有效性
        char[] charArray = s.toCharArray();
        // 用 128 是测试出来的，说明题目中的字符只有 a-zA-Z
        freq = new int[128];
        for (char c : charArray) {
            freq[c]++;
        }

        int len = charArray.length;
        quickSort(charArray, 0, len - 1);
        return new String(charArray);
    }

    private void quickSort(char[] charArray, int left, int right) {
        if (left >= right) {
            return;
        }
        int randomIndex = left + RANDOM.nextInt(right - left + 1);
        swap(charArray, randomIndex, left);

        // 循环不变量定义
        // all in [left + 1, lt] 的频数 > pivot 的频数
        // all in [lt + 1, i) 的频数 = pivot 的频数
        // all in [gt, right] 的频数 < pivot 的频数
        int pivot = charArray[left];
        int lt = left;
        int gt = right + 1;

        int i = left + 1;
        while (i < gt) {
            // 只需要在这句话外面套一层 freq [] ，其它逻辑和快速排序一样
            if (freq[charArray[i]] > freq[pivot]) {
                lt++;
                swap(charArray, i, lt);
                i++;
            } else if (charArray[i] == pivot) {
                i++;
            } else {
                gt--;
                swap(charArray, i, gt);
            }
        }
        swap(charArray, left, lt);
        // 注意这里，大大减少了分治的区间
        quickSort(charArray, left, lt - 1);
        quickSort(charArray, gt, right);
    }

    private void swap(char[] charArray, int index1, int index2) {
        char temp = charArray[index1];
        charArray[index1] = charArray[index2];
        charArray[index2] = temp;
    }
}

• 下面的问题用于复习循环不变量。
  • 「力扣」第 26 题：删除排序数组中的重复项（简单）
  • 「力扣」第 27 题：移除元素（简单）
  • 「力扣」第 283 题：移动零（简单）

参考资料

• 在《算法导论》里大量使用了「循环不变量」这个概念说明和证明问题。但「循环不变量」并不是一个很高深的概念，其实我们很多时候，在编写代码的过程中都在不自觉地维护了变量的定义。「循环不变量」只是一个学术化的名字而已，设计清楚「循环不变量」，可以帮助我们写出正确的代码。
  • 《算法导论》第 2.1 节 插入排序
  • 《算法导论》第 2.3.1 节分治法
  • 《算法导论》第 6.3 节 建堆
  • 《算法导论》第 7.1 节 快速排序的描述
• 事实上，一个广泛应用「循环不变量」概念的算法就是 二分查找，二分查找有些时候不能写对，与不能维持循环不变量的定义有很大的关系。