https://leetcode-cn.com/probl...这道题叫做荷兰国旗问题，由Dijkstra提出（在非negativeweightgraph他还提出了Dijkstra算法和银行家算法来防止死锁）。荷兰国旗有三种颜色。这道题是对一个只有0、1、2三个数的数组进行排序。方法一：二次遍历，统计数+生成新数二次遍历的方法比较简单。第一次遍历统计每个数字出现的次数，下一次遍历可以直接根据次数生成新的数字。完全不需要交换号码。类解决方案：defsortColors(self,nums:List[int])->None:"""不要返回任何东西，而是就地修改nums。"""cnt=[0]*3forninnums:cnt[n]+=1i=0forcurinrange(3):forjinrange(cnt[cur]):nums[i]=curi+=1方法一：一次遍历，三个指针l指向0右，r指向2的最左边，cur为当前查看的数字。如果当前数是0，交换到l，如果是2，交换到r。如果是1，则不要移动。但是这里和l交换和r交换的区别是，在和l交换后，cur加1跳过刚刚交换过来的数组，但是和r交换不行，因为和l交换的数都是从上一个过来的，肯定是1，不用再找了。classSolution:defsortColors(self,nums:List[int])->None:"""不要返回任何东西，而是就地修改nums。"""l=cur=0r=len(nums)-1whilecur<=r:ifnums[cur]==0:ifcur!=l:nums[cur],nums[l]=nums[l],nums[cur]cur+=1l+=1elifnums[cur]==2:nums[cur],nums[r]=nums[r],nums[cur]r-=1else:cur+=1欢迎来到我的博客：https://codeplot.top/我的博客主题分类：https://codeplot.top/categories/%E5%88%B7%E9%A2%98/
