LeetCode 75. 颜色分类（中）

计数排序的经典问题

题目

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

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

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

示例

示例:

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

考察知识点

排序、双指针、数组

核心思想

方法一、计数排序的两趟扫描算法
常数空间实现计数排序的一趟扫描算法，就可以解这个问题。

方法二、荷兰国旗问题

本解法的思路是沿着数组移动 curr 指针，若nums[curr] = 0，则将其与 nums[p0]互换；若 nums[curr] = 2 ，则与 nums[p2]互换。

算法

  • 初始化0的最右边界：p0 = 0。在整个算法执行过程中 nums[idx < p0] = 0.
  • 初始化2的最左边界 ：p2 = n - 1。在整个算法执行过程中 nums[idx > p2] = 2.
  • 初始化当前考虑的元素序号 ：curr = 0.
  • While curr <= p2 :
    • 若 nums[curr] = 0 ：交换第 curr个 和 第p0个 元素，并将指针都向右移。
    • 若 nums[curr] = 2 ：交换第 curr个和第 p2个元素，并将 p2指针左移 。
    • 若 nums[curr] = 1 ：将指针curr右移。

Python版本

  • 方法一计数排序的实现
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
from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        colors = [0 for _ in range(3)]
        for i in nums: colors[i] += 1
        cur = 0  # 设置一个cur来控制填充
        for i in range(3):
            for _ in range(colors[i]):
                nums[cur] = i
                cur += 1


Input = [[2, 0, 2, 1, 1, 0]]
Answer = [[0, 0, 1, 1, 2, 2]]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        solution.sortColors(Input[i])
        if Input[i] == Answer[i]:
            print(True)
        else:
            print(False)
            print(Answer[i])

时间复杂度：\(O(n)\)，只扫描了一趟。
空间复杂度：\(O(1)\)。
执行用时 :32 ms, 在所有 Python3 提交中击败了87.55%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了5.19%的用户

  • 方法二荷兰国旗算法的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        '''
        荷兰三色旗问题解
        '''
        # 对于所有 idx < p0 : nums[idx < p0] = 0
        # curr是当前考虑元素的下标
        p0 = curr = 0
        # 对于所有 idx > p2 : nums[idx > p2] = 2
        p2 = len(nums) - 1

        while curr <= p2:
            if nums[curr] == 0:
                nums[p0], nums[curr] = nums[curr], nums[p0]
                p0 += 1
                curr += 1
            elif nums[curr] == 2:
                nums[curr], nums[p2] = nums[p2], nums[curr]
                p2 -= 1
            else:
                curr += 1

时间复杂度 :由于对长度 N的数组进行了一次遍历，时间复杂度为 \(O(N)\)。
空间复杂度 :由于只使用了常数空间，空间复杂度为 \(O(1)\)。
执行用时 :32 ms, 在所有 Python3 提交中击败了87.55%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了5.19%的用户

参考链接

Grandyang
LeetCode官方题解