75. 颜色分类 [medium]

荷兰国旗问题

https://leetcode-cn.com/problems/sort-colors/

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

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

注意: 不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。你能想出一个仅使用常数空间的一趟扫描算法吗？

通过次数94,792 | 提交次数171,853

Second Try

2020-07-10

其实第一眼就觉得可以用两个指针，左边和右边分别递推。

但是在怎么原地排序方面头疼了很久，总觉得被干涉到了，没想出该怎么处理。

看了题解，发现确实也是这么做的，于是一路写下去，在交换的时候仍然遇到许多bug.

重点是在交换右侧元素的时候，前进指针需要暂停，对交换回来的元素继续进行判断，不然该元素直接就被跳过去了。而交换左侧元素的时候，必然不需要考虑，因为都是被遍历过的，肯定是1.

贡献了几个错误提交后，终于搞定了。精神有点疲倦，在这么小的题目上。。。

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        
        # 其实是三路快排在分隔时候的做法，但是原地更新还是挺不习惯
        left, right = 0, len(nums) - 1
        start = 0 
        while start <= right:  # 等于的时候，该元素还没被处理
            if nums[start] == 0:
                # 跟左侧交换的时候，左侧的元素肯定被遍历过了，start继续往前即可
                nums[left], nums[start] = nums[start], nums[left]
                left += 1
                start += 1
            elif nums[start] == 2:
                # 跟右侧交换的时候，不知道换过来的是什么，因此start原地踏步，再判断一波
                nums[start], nums[right] = nums[right], nums[start]
                right -= 1
            else:
                start += 1
        return nums 

执行用时：20 ms, 在所有 Python 提交中击败了73.16%的用户
内存消耗：13 MB, 在所有 Python 提交中击败了28.57%的用户

First Try

2020-07-10

按提示写的方法，不然还真想不到竟然可以重新替换写入，都改变了之前的内存id了。

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        
        counts = collections.defaultdict(int)
        for n in nums:
            counts[n] += 1
        i = 0
        for n in [0, 1, 2]:
            while counts[n] > 0:
                nums[i] = n 
                i += 1
                counts[n] -= 1
        return nums

执行用时：28 ms, 在所有 Python 提交中击败了18.94%的用户
内存消耗：12.9 MB, 在所有 Python 提交中击败了28.57%的用户

75. 颜色分类 [medium]​

Second Try​

First Try​

75. 颜色分类 [medium]

Second Try

First Try