今日题目

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

思路

本题中数组内只存在三种元素，因此可以利用桶排序来解决问题。

方法

只需用一个桶统计每个数字出现的次数，再将这些数字依次填回数组即可。

复杂度

  • 时间复杂度：$O(N)$，N 为数组的长度。
  • 空间复杂度：$O(Num)$，Num 为不同数字的种类数。

代码


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