M-75. Sort Colors

Sort Colors - LeetCodeLeetCode

# 1. counting sort, O(n), O(k)
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        count_lst = [0,0,0]
        for i in nums:
            count_lst[i] += 1
        
        index = 0
        for i, v in enumerate(count_lst):
            while v > 0:
                nums[index] = i
                v -= 1
                index += 1

# 2. One Pass, O(n), O(1)
# 上面图片叙述的很清晰. 多说一句的是: p0指向数组中最右边一个0的右边一格, p2指
# 向最左侧2的左边一格
# 这里有一个关于multiple assignment的讲解, 本质上是tuple赋值:
# https://treyhunner.com/2018/03/tuple-unpacking-improves-python-code-readability/
# 这篇文章也不错: https://treyhunner.com/2016/04/how-to-loop-with-indexes-in-python/
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Dutch National Flag problem solution.
        """
        # for all idx < p0 : nums[idx < p0] = 0
        # curr is an index of element under consideration
        p0 = curr = 0
        # for all idx > p2 : nums[idx > p2] = 2
        p2 = len(nums) - 1

        while curr <= p2:
            if nums[curr] == 0:
                nums[p0], nums[curr] = nums[curr], nums[p0]
                p0 += 1
                curr += 1
            elif nums[curr] == 2:
                nums[curr], nums[p2] = nums[p2], nums[curr]
                p2 -= 1
            else:
                curr += 1