目要求將給定的數組按顏色進行排序,顏色只有三種:紅色(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;
}
}
}
};