每日一道算法之--颜色分类

排序

Word count: 995Reading time: 4 min

 2020/04/07   Share

颜色分类

力扣第75题 : https://leetcode-cn.com/problems/sort-colors/

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

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

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

示例:

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

1. 计数排序

这道题其实说白了就是排序,可以按照普通的排序直接做,但是它这里只会出现0, 1, 2 这三种数字,所以使用计数排序是一个很好的选择。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        bucket = [0] * 3
        sorted_index = 0
        for num in nums:
            bucket[num] += 1
        for index, count in enumerate(bucket):
            while count > 0:
                nums[sorted_index] = index
                sorted_index += 1
                count -= 1

复杂度分析

时间复杂度: 扫描一遍数组算出各个数字的次数,时间复杂度为O(N),然后在重写数组,所以总的时间为O(N)

空间复杂度: 用了一个列表来作为桶,长度为3,所以空间复杂度为O(1)

2. 一次遍历

因为只有0, 1, 2 这三个数字,所以0肯定为最左边,2为最右边,我们使用两个指针，一个指向左，一个指向右边，当我们遍历数组时,如果当前数位0,则将其与左边的数交换,如果为2就和右边的数交换。我后来看了题解，是叫荷兰国旗问题。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        head, tail = 0, len(nums) - 1
        index = 0
        # 这里退出的条件是index而不是head
        while index <= tail:
            if nums[index] == 0:
                nums[head], nums[index] = nums[index], nums[head]
                head += 1
                # 这里索引也要加1,因为数组是从头开始排序的
                index += 1
            elif nums[index] == 2:
                nums[tail], nums[index] = nums[index], nums[tail]
                tail -= 1
            else:
                index += 1

复杂度分析

时间复杂度:由于对长度 N 的数组进行了一次遍历，时间复杂度为O(N)。

空间复杂度: 用了一个列表来作为桶,长度为3,所以空间复杂度为O(1)。

3. 三路快排

参考自 https://leetcode-cn.com/problems/sort-colors/solution/kuai-su-pai-xu-partition-guo-cheng-she-ji-xun-huan/
作者：liweiwei1419

如果循环不变量是这样定义的：
所有在子区间 [0, zero) 的元素都等于 0；
所有在子区间 [zero, i) 的元素都等于 1；
所有在子区间 [two, len - 1] 的元素都等于 2。

编码的时候，zero 和 two 初始化的值就应该保证上面的三个子区间全为空。
在遍历的过程中，“索引先加减再交换”、还是“先交换再加减”就看初始化的时候变量在哪里。
退出循环的条件也看上面定义的循环不变量，在 i == two 成立的时候，上面的三个子区间就正好“不重不漏”地覆盖了整个数组，并且给出的性质成立，题目的任务也就完成了。

from typing import List


class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        # all in [0, zero) = 0
        # all in [zero, i) = 1
        # all in [two, len - 1] = 2

        def swap(nums, index1, index2):
            nums[index1], nums[index2] = nums[index2], nums[index1]

        size = len(nums)
        if size < 2:
            return

        # 为了保证初始化的时候 [0, zero) 为空，设置 zero = 0，
        # 所以下面遍历到 0 的时候，先交换，再加
        zero = 0

        # 为了保证初始化的时候 [two, len - 1] 为空，设置 two = len
        # 所以下面遍历到 2 的时候，先减，再交换
        two = size

        i = 0
        # 当 i == two 上面的三个子区间正好覆盖了全部数组
        # 因此，循环可以继续的条件是 i < two
        while i < two:
            if nums[i] == 0:
                swap(nums, i, zero)
                i += 1
                zero += 1
            elif nums[i] == 1:
                i += 1
            else:
                two -= 1
                swap(nums, i, two)

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/04/07/algorithm-75/

发表日期：April 7th 2020, 3:09:44 pm

更新日期：April 7th 2020, 3:10:34 pm

Next Post

每日一道算法之--删除排序链表中的重复元素 II
Previous Post

数据结构学习笔记---散列表

CATALOG

1. 颜色分类

