给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
<pre style="box-sizing: border-box; overflow: auto; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; display: block; padding: 9.5px; margin: 0px 0px 10px; line-height: 1.42857; color: rgb(51, 51, 51); word-break: break-all; word-wrap: break-word; background-color: rgb(245, 245, 245); border: 1px solid rgb(204, 204, 204); border-radius: 4px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]</pre>
进阶：
- 一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 - 你能想出一个仅使用常数空间的一趟扫描算法吗？
class Solution:
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
num0, num2 = 0, 0
for i,n in enumerate(nums):
if n == 0:
num0 += 1
if n == 2:
num2 += 1
nums[i] = 1
if num0:
nums[:num0] = [0] * num0
if num2:
nums[-num2:] = [2] * num2
class Solution:
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
n0,n1,n2 = 0,0,0
for i in range(len(nums)):
# print(i,n0,n1,n2,nums)
if nums[i] == 0:
nums[n2] = 2
nums[n1] = 1
nums[n0] = 0
n0+=1
n1+=1
n2+=1
elif nums[i] == 1:
nums[n2] = 2
nums[n1] = 1
n1+=1
n2+=1
elif nums[i] == 2:
nums[n2] = 2
n2+=1
网友评论