75.颜色分类

题目

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

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

必须在不使用库内置的 sort 函数的情况下解决这个问题。

解题思路

读完题目，最容易想到的通用解法便是直接对数组进行排序。这里使用插入排序算法。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        for i in range(1,n):
            for j in range(i,0,-1):
                if nums[j] < nums[j-1]:
                    nums[j], nums[j-1] = nums[j-1], nums[j]
                else:
                    break

插入排序算法大致思路如下：该算法不断维护一个有序数组，我们假设前i个数是升序（降序）排列，我们将i从1逐渐增大至原来数组的大小n时，那么我们便会得到原来数组的排序结果。在i增大的每个循环中，我们需要把第i个数（待插入的数）拿出来，将其与前面的一个数进行比较，如果小于（大于）便交换两个数，循环这个过程，直到前面一个数不满足前面的条件为止，即说明此时该元素的位置符合整个前i个数的升序（降序）排列。

复杂度分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

解题思路【学习】

75. 颜色分类（官方题解）

partition

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NpWhBEtE-1681999331792)(C:UsersMSTIFIYAppDataRoamingTypora ypora-user-imagesimage-20230420205617921.png)]

本算法的关键在于对分区定义的遵循，也称循环不变量。 注意，在最开始，应该使每个区间为空。循环变量i指向待划分的元素。

from typing import List
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def swap(nums, index1, index2):
            """交换两个元素的位置"""
            nums[index1], nums[index2] = nums[index2], nums[index1]

        n = len(nums)
        if n < 2:
            """对于元素个数小于2的数组不需要排序"""
            return
        # all in [0, p0) == 0
        # all in [p0, i) == 1
        # all in (p2, n - 1] == 2
        p0 = 0
        i = 0
        p2 = n - 1
        
        while i <= p2:
            if nums[i] == 0:
                swap(nums, i, p0)
                i += 1
                p0 += 1
            elif nums[i] == 1:
                i += 1
            else:
                swap(nums, i, p2)
                p2 -= 1

作者：liweiwei1419
链接：https://leetcode.cn/problems/sort-colors/solution/kuai-su-pai-xu-partition-guo-cheng-she-ji-xun-huan/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$