【LeetCode 中级算法】颜色分类

【中级算法】​​颜色分类​​

想法：

• 01.使用三指针解决这个问题
  i指针指向最小值；j指针指向最大值，k指针在二者之间移动，进行数据的交换

• 02.这道题有点儿我的解法还欠妥，需要再完善一下。
  为了解决上面这个问题，我投懒了一下，人为保证输入的数据中有0,2两种数据，然后在得到有序的数据上，再进行删除。这样就可以保证排序的正确性。【但是这点儿操作有点儿冗余，如果中间的判断过程完善的话，应该是不需要插入再删除的那四行代码】

• python中数据的交换可以直接用 ​​a,b=b,a​​的方式，不用使用中间变量。

from typing import List
from queue import Queue
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums.insert(0,0)
nums.append(2)
i ,k = 0,1
j = len(nums) - 1
# nums[i] 左往右第一个不是0的值
# nums[j] 右往左第一个不是2的值
while(k < len(nums)):
# 始终保证 nums[i] 是在最小值位置
# 从左往右
while i<len(nums) and nums[i] ==0:
i+=1
# 这个时候 nums[i]!=0

# 从右往左
while j>=0 and nums[j] == 2:
j-=1 #

# BUG： 因为这个必须有0和2才交换，所以对于样例 [2,1] 这种就失败了
if nums[k] == 0 and i < len(nums) and k>i : # 与nums[i]交换
nums[k] ,nums[i] = nums[i],nums[k]
i+=1
k-=1
elif nums[k] == 2 and j>=0 and k<j: # 与nums[j] 交换
nums[k] ,nums[j] = nums[j],nums[k]
j-=1
k-=1
k+=1
del nums[0]
del nums[-1]
print(nums)

s = Solution()
s.sortColors([2,0,2])