LeetCode0075.SortColors颜色分类【Medium】【Python】【Dutchflag】问题LeetCode给定一个包含n个对象的数组，颜色为红色，白色或蓝色，就地对它们进行排序，使得对象相同颜色的相邻，颜色顺序为红、白、蓝。在这里，我们将使用整数0、1和2分别表示红色、白色和蓝色。注意：你不应该使用库的排序函数来解决这个问题。示例：输入：[2,0,2,1,1,0]输出：[0,0,1,1,2,2]跟进：一个相当直接的解决方案是使用计数排序的两次通过算法。首先，迭代0、1和2的数组计数，然后用0的总数覆盖数组，然后是1，然后是2。你能想出一个只使用常量空间的一次性算法吗？题目给定一个包含红、白、蓝共n个元素的数组，将它们原地排序，使相同颜色的元素相邻，并按照红、白、蓝的顺序排列。在这个问题中，我们使用整数0、1和2分别表示红色、白色和蓝色。注意：您不能使用代码库中的排序函数来解决此问题。示例：输入：[2,0,2,1,1,0]输出：[0,0,1,1,2,2]高级：一个直观的解决方案是使用计数排序的二次算法。首先迭代计算0、1、2元素的个数，然后按照0、1、2的顺序重写当前数组。你能想出一个只使用常量空间的onepass算法吗？思路荷兰国旗有left、mid、right三个指针，其中mid指针用来遍历数组。mid指向0，交换left和mid，left++，mid++mid指向1，不做任何交换，mid++mid指向2，交换right和mid，当right--mid指向2时，只有right--就可以了，不需要mid++，因为如果交换的值为0，还需要进一步处理。有关荷兰国旗的详细信息，请参阅Wiki。也可以直接分类来做，分为红、白、蓝三类。时间复杂度:O(n)空间复杂度:O(1)Python代码classSolution(object):defsortColors(self,nums):""":typenums:List[int]:rtype:None不返回任何东西，就地修改nums。"""##法一：分类#red,white,blue=0,0,0#foriinnums:#ifi==0:#red+=1#elifi==1:#white+=1#foriinrange(red):#nums[i]=0#foriinrange(red,red+white):#nums[i]=1#foriinrange(red+white,len(nums)):#nums[i]=2#法二：荷兰旗问题三指针left,mid,right=0,0,len(nums)-1whilemid<=right:如果nums[mid]==0:nums[left],nums[mid]=nums[mid],nums[left]left+=1mid+=1elifnums[mid]==1:mid+=1else:nums[中],nums[右]=nums[右],nums[mid]right-=1#只需要向右向左移动一位，mid不需要移动代码地址github链接
