Leetcode 75. Sort Colors

Sort Colors :

目要求將給定的數組按顏色進行排序，顏色只有三種：紅色（0）、白色（1）、藍色（2）。

給你一個由整數 0、1 和 2 組成的數組 nums，請你在原地將該數組盡可能地排列成數字 0、1 和 2。

Python

方法一 :計數排序

先統計每種顏色的數量，然後遍歷數組，將每種顏色填充到數組中。

1. 創建一個長度為 3 的數組 counts，用來統計每種顏色的數量。

2. 然後遍歷原數組 nums，統計每種顏色的數量。

3. 最後遍歷 counts 數組，將每種顏色填充到原數組 nums 中。

class Solution:
    def sortColors(self, nums: List[int]) -> None:

        counts = [0, 0, 0]       
        for num in nums:         #長度為 3 的數組，統計每種顏色
            counts[num] += 1
        
        i = 0
        for idx, count in enumerate(counts): #每種顏色填充到原數組 nums
            for _ in range(count):
                nums[i] = idx
                i += 1

方法二 : 三指標

zero指向0的最右邊，two指向2的最左邊，one指向當前位置，如果one指向的是0和zero交換，是2和two交換，是1則繼續

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        
        zero, one, two = 0, 0, len(nums) - 1
        while one <= two:
            if nums[one] == 0:
                nums[zero], nums[one] = nums[one], nums[zero]
                zero += 1
                one += 1
            elif nums[one] == 2:
                nums[one], nums[two] = nums[two], nums[one]
                two -= 1
            else:
                one += 1

C++

方法一 :計數排序

先遍歷數組，統計紅、白、藍三種顏色球的數量，然後根據數量對原數組進行覆蓋排序

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int cnt[3] = {0, 0, 0};
        for (int i = 0; i < nums.size(); ++i) {
            ++cnt[nums[i]];
        }
        int index = 0;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < cnt[i]; ++j) {
                nums[index++] = i;
            }
        }
    }
};

方法二 : 雙指標

定義兩個指針 p0 和 p2，分別指向排好序的紅球和藍球的位置，初始時 p0 和 p2 分別指向數組的第一個和最後一個元素，然後定義一個指針 curr，從數組的第一個元素開始遍歷。

遍歷時，如果 nums[curr] 為紅球，那麼將其交換到 p0 的位置，然後 p0 和 curr 都向右移動一位；如果 nums[curr] 為白球，那麼 curr 向右移動一位；如果 nums[curr] 為藍球，那麼將其交換到 p2 的位置，然後 p2 向左移動一位，此時 curr 不移動，因為此時 curr 交換過來的元素可能是紅球或者白球。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int p0 = 0, p2 = nums.size() - 1, curr = 0;
        while (curr <= p2) {
            if (nums[curr] == 0) {
                swap(nums[curr], nums[p0]);
                ++p0;
                ++curr;
            } else if (nums[curr] == 2) {
                swap(nums[curr], nums[p2]);
                --p2;
            } else {
                ++curr;
            }
        }
    }
};