LeetCode 0075. Sort Colors颜色分类【Medium】【Python】【荷兰旗】
Given an array 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.
Note: You are not suppose to use the library‘s sort function for this problem.
Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶:
荷兰旗
三个指针,left,mid,right,其中 mid 指针用来遍历数组。
mid 指向 2 的时候,只需要 right-- 就行,而不需要 mid++,因为如果交换过来的是 0,需要做进一步处理。
关于荷兰旗问题,详情请参考Wiki。
也可以直接用分类做,分成 red,white,blue 三类。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
# # 法一:分类
# red, white, blue = 0, 0, 0
# for i in nums:
# if i == 0:
# red += 1
# elif i == 1:
# white += 1
# for i in range(red):
# nums[i] = 0
# for i in range(red, red+white):
# nums[i] = 1
# for i in range(red+white, len(nums)):
# nums[i] = 2
# 法二:荷兰旗问题 三指针
left, mid, right = 0, 0, len(nums)-1
while mid <= right:
if nums[mid] == 0:
nums[left], nums[mid] = nums[mid], nums[left]
left += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[right] = nums[right], nums[mid]
right -= 1 # 只需要right往左移一位就行,mid不需要动
LeetCode | 0075. Sort Colors颜色分类【Python】
原文:https://www.cnblogs.com/wonz/p/12313281.html