【LeetCode 】颜色分类

哈妹 lv.1

发布时间：2022-11-02 00:50:19 276

题目

【中级算法】颜色分类

想法

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                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])

文章来源： https://blog.51cto.com/lawsonabs/5806925

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。