LeetCode 75. 颜色分类(三指针)

Description

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

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

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

示例: 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sort-colors 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1 枚举

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

Solution 2 三指针

三个指针（p0, p2 和curr）来分别追踪0的最右边界，2的最左边界和当前考虑的元素。

class Solution: def sortColors(self, nums: List[int]) -> None: p0 = curr = 0 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: # 此时注意：curr指针不动，只有p2收缩 nums[curr], nums[p2] = nums[p2], nums[curr] p2 -= 1 else: curr += 1 # 作者：LeetCode # 链接：https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode/ # 来源：力扣（LeetCode） # 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。