Today’s problem

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

Intuition

In this case, we know that there are only three elements in the list, so we can use bucket sort to solve this problem.

Approach

All we need is to use a bucket to calculate the number of times each number exists, then we put these numbers into the array.

Complexity

  • Time complexity: $O(N)$, N is the length of the array.
  • Space complexity: $O(Num)$, Num is the number of different numbers.

Code


class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # nums.sort()
        cnt = [0,0,0]
        for num in nums:
            cnt[num] += 1

        cnt[1] += cnt[0]
        cnt[2] += cnt[1]

        cur = 0

        for i in range(len(nums)):
            while i >= cnt[cur]:
                cur += 1
            nums[i] = cur

image.png