LeetCode50天刷题计划（Day 41 —颜色分类（13.00-14.10）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

挺有意思的一个题

一、题目

颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例

示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]

提示

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

进阶：

你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？

二、思路

考虑到双指针将0与2交换了，但具体的实现不太明确，所以代码写的很乱，也不是标准的O(n)，后来才想清楚

1.双指针遍历

由于只有三个元素，因此一个指针从后往前遍历，一个指针从前往后遍历，
#遇到00、01：i后移一位，j不变
#遇到02：i后移一位，j前移一位
#遇到11、12、22：i不变，j前移一位
遇到以上三种情况的相反，先交换，再做操作，如：遇到10：交换位置，i后移一位，j不变
遇到11需要先寻找i后j前第一个不等于1的数,将他与j交换
时间复杂度不止O(n)

2.一次遍历

一个指针从前向后遍历，再两个指针分别标记0的末位和2的开头
遍历到0或2就跟目标地元素交换位置,这样就可以保证找到所有的0和2，分别放在first之前和last之后
注意i遍历到last就可以停止，因为后面全都是2了
但是，如果遇到2，将2与last交换，新的数从后面到前面，它可能是 2，也可能是 0，但此时我们已经结束了交换，开始遍历下一个元素 ，就会漏掉这个元素了，这样就会得到错误的答案。

因此，当找到 2 时，我们需要不断地将其与last进行交换，直到新的i不为 2。此时，如果新的i为 0，与first交换；如果新的i为 1，那么就不需要进行任何后续的操作。

三、代码

1.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i,j = 0,len(nums)-1
        while(i<j):
            if(nums[i]==1 and nums[j]==1): #同时指向1
                temp=i+1
                while(nums[temp] == 1 and temp<j): #寻找i后第一个不等于1的数,需要小于j
                    temp+=1
                nums[temp],nums[j]=nums[j],nums[temp]
            if(nums[i]>nums[j]): #顺序不对先交换
                nums[i],nums[j] = nums[j],nums[i]
            if(nums[i]==0): #按规律移动指针
                if(nums[j]==2):
                    j-=1
                i+=1
            else:
                j-=1         
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i,first,last=0,0,len(nums)-1
        while(i<=last):
            while(nums[i]==2 and i<=last):
                nums[i],nums[last]=nums[last],nums[i]
                last-=1   
            if(nums[i]==0): #0,和first换
                nums[i],nums[first]=nums[first],nums[i]
                first+=1
            i+=1
1
2
3
4
5
6
7
8
9
10
11
12
13
14