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(n^2) O(n2)
• 空间复杂度：$O(1)$

解题思路【学习】

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

partition

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NpWhBEtE-1681999331792)(C:\\Users\\MSTIFIY\\AppData\\Roaming\\Typora\\typora-user-images\\image-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] == 2p0 = 0i = 0p2 = n - 1while i <= p2:if nums[i] == 0:swap(nums, i, p0)i += 1p0 += 1elif nums[i] == 1:i += 1else: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)$