LeetCode 75 颜色分类 [Swift]
2019-09-26
题目
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
思路
本题如果使用排序算法，有很多种解题方法。但就像题目进阶提示部分说明的，如何设计出一个时间和空间复杂度都优良的算法，是本题关键所在。
三个数字排序，把 0 全部放在数组头部，2 放在数组尾部，剩下的 1 自然处在中间。
具体到代码实现：我们引入三个指针，cur 用来从头到尾遍历数组，p0 的左侧全部是 0， p2 的右侧全部是 2 ，p0 和 p2 初始位置，分别置于数组头和尾。伴随 cur 的遍历，将 cur 指向的不符合要求的数字与 p0 或 p2 指向的数字 swap。
最终的时间复杂度为 O(n)，空间复杂度为 O(1)。
附录代码如下:
class Solution {
func sortColors(_ nums: inout [Int]) {
var p0 = 0
var cur = 0
var p2 = nums.count - 1
var tmp = 0
while cur <= p2 {
if nums[cur] == 0 {
tmp = nums[p0]
nums[p0] = nums[cur]
nums[cur] = tmp
p0 += 1
cur += 1
} else if (nums[cur] == 2) {
tmp = nums[cur]
nums[cur] = nums[p2]
nums[p2] = tmp
p2 -= 1
} else {
cur += 1
}
}
}
}