ARTS #76 | 关于生财日历

Algorithm

本周选择的算法题是：Sort Colors

规则如下：

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Follow up:

Could you solve this problem without using the library’s sort function?
Could you come up with a one-pass algorithm using only O(1) constant space?

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Example 3:

Input: nums = [0]
Output: [0]

Example 4:

Input: nums = [1]
Output: [1]

Constraints:

n == nums.length
1 <= n <= 300
nums[i] is 0, 1, or 2.

Solution

这题很简单也很有趣：

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

因为值只有固定三个，通过两次循环很直观就能解决，但题目要求了 one-pass，可以修改如下：

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i, low, high = 0, 0, len(nums)-1
        while i <= high:
            if nums[i] == 0:
                nums[i], nums[low] = nums[low], nums[i]
                i +=1; low += 1
            elif nums[i] == 2:
                nums[i], nums[high] = nums[high], nums[i]
                high -= 1
            else:
                i += 1