LeetCode刷题实战75：颜色分类
程序IT圈
共 5078字，需浏览 11分钟
·
2020-10-25 02:29
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 颜色分类，我们先来看题面：
https://leetcode-cn.com/problems/sort-colors/
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Follow up:
Could you solve this problem without using the library's sort function?
Could you come up with a one-pass algorithm using only O(1) constant space?
题意
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
解题
桶排序
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
bucket = [0 for _ in range(3)]
for i in nums:
bucket[i] += 1
ret = []
for i in range(3):
ret += [i] * bucket[i]
nums[:] = ret[:]
的耗时，桶排序只遍历了两次数组，明显要快得多。但遗憾的是这并不是最佳的方法，题目当中明确说了，还有只需要遍历一次原数组的方法。two pointers
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
l, r = 0, len(nums)-1
i = 0
while i < len(nums):
if i > r:
break
# 如果遇到0，则和左边交换
if nums[i] == 0:
nums[l], nums[i] = nums[i], nums[l]
l += 1
# 如果遇到2，则和右边交换
# 交换之后i需要-1，因为可能换来一个0
elif nums[i] == 2:
nums[r], nums[i] = nums[i], nums[r]
r -= 1
continue
i += 1
的算法，相差的只是一个常数。遍历的次数只是构成常数的部分之一。维护区间
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 记录0，1和2的末尾位置
zero, one, two = -1, -1, -1
n = len(nums)
for i in range(n):
# 如果摆放0
# 那么1和2都往后平移一位，让一个位置出来摆放0
if nums[i] == 0:
nums[two+1] = 2
nums[one+1] = 1
nums[zero+1] = 0
zero += 1
one += 1
two += 1
elif nums[i] == 1:
nums[two+1] = 2
nums[one+1] = 1
one += 1
two += 1
else:
nums[two+1] = 2
two += 1
总结
上期推文：
评论