leetcode-75

75. 颜色分类

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

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

原地算法不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入的一种算法操作。

示例：

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

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

输入：nums = [0]
输出：[0]

输入：nums = [1]
输出：[1]

​

解法

解法一

当成排序去做。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums_len = len(nums)
        for i in range(nums_len):
            for j in range(i+1,nums_len):
                if nums[i]>nums[j]:
                    nums[i] = nums[i] + nums[j]
                    nums[j] = nums[i] - nums[j]
                    nums[i] = nums[i] - nums[j]

        return nums

官方解法二：单指针

用一个指针ptr分两次遍历数组，第一次将0交换到前面，ptr指向的位置，代表0的边界。

第二次交换将1交换到前面，ptr指向的位置，代表1的边界。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums_len = len(nums)
        ptr = 0
        for i in range(nums_len):
            if nums[i] == 0:
                nums[ptr], nums[i] = nums[i],nums[ptr]
                ptr+=1
        
        for i in range(nums_len):
            if nums[i] == 1:
                nums[ptr],nums[i] = nums[i],nums[ptr]
                ptr+=1


        return nums

官方解法三：双指针

用一次遍历，来解决这个问题，

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums_len = len(nums)
        ptr = 0
        ptr0 = ptr1 = 0
        
        
        for i in range(nums_len):
            # 交换1,
            if nums[i] == 1:
                nums[ptr1],nums[i] = nums[i],nums[ptr1]
                ptr1 += 1
            elif nums[i] == 0:
                nums[ptr0],nums[i] = nums[i],nums[ptr0] # 交换0，在交换0的时候有可能把1换到后面

                # 在时候在把1换到前面
                if ptr0<ptr1:
                    nums[ptr1],nums[i] = nums[i],nums[ptr1]
                ptr0 += 1
                ptr1 += 1

        return nums