LeetCode 75. Sort Colors
Description
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:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with a one-pass algorithm using only constant space?
描述
给定一个具有红色，白色或蓝色的n个对象的数组，对它们进行就地排序，使相同颜色的对象相邻，颜色顺序为红色，白色和蓝色。
这里，我们将使用整数0,1和2分别表示红色，白色和蓝色。
注意：您不应该使用库的排序功能来解决此问题。
思路
- 此题题意是给定三种不同的数，按照从小到大顺序排序.
- 不能使用库函数.
- 额外要求：时间复杂度：仅遍历一趟数组，空间：O(1).
- 我们用zero来记录已经到达最终位置的0的下一个索引.
- 我们用one 来记录已经到达最终位置的1的下一个索引.
- 即nums[0:zero-1]全部是0，且它们已经到达了最终的位置.
- nums[zero:one-1]全部是1，且他们已经到达了最终的位置.
- 我们从one开始遍历数组
若nums[i]==0
- 则把已经到达最终位置的1的后一个元素num[one]付给nums[i]
- 把已经到达最终位置的0的后一个元素num|[zero]给nums[one]
- 把nums[zero]置为0
若nums[i]==1
- 则把已经到达最终位置的1的后一个元素num[one]付给nums[i]
- 把nums[one]置为1
class Solution:
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
if not nums:
return
# zero表示已经到达最终位置的0的下一个位置
# nums[0:zero-1]之间的数字都是0，它们都已经到达了最终位置
# one 表示已经到达最终位置的1的下一个位置
# nums[zero:one-1]之间的数字都是1，它们都已经到达了最终位置
zero, one, length = 0, 0, len(nums)
# 只需要遍历一次
for i in range(length):
if nums[i] == 0:
# 如果当前是0，则把当前位置的值置为nums[one],把nums[one]置为nums[zero]
# 把nums[zero]置为0
nums[i], nums[one], nums[zero] = nums[one], nums[zero], 0
zero += 1
one += 1
# 如果当前位置是1，则把当前位置置为nums[one],把nums[one]置为0
elif nums[i] == 1:
nums[i], nums[one] = nums[one], 1
one += 1
