75. Sort Colors
給定一個包含 n 個物件的陣列 nums，這些物件被染成紅色、白色或藍色，請對它們進行原地排序，使得相同顏色的物件相鄰，並且顏色的順序為紅色、白色和藍色。
我們將使用整數 0、1 和 2 分別代表紅色、白色和藍色。
你必須在不使用庫排序函數的情況下解決這個問題。
範例 1：
輸入：nums = [2,0,2,1,1,0] 輸出：[0,0,1,1,2,2]
Python
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[high], nums[mid] = nums[mid], nums[high]
high -= 1
16.45MB, 30ms
C++
#include <vector>
using namespace std;
class Solution {
public:
void sortColors(vector<int>& nums) {
int low = 0, mid = 0, high = nums.size() - 1;
while (mid <= high) {
if (nums[mid] == 0) {
swap(nums[low], nums[mid]);
low++;
mid++;
} else if (nums[mid] == 1) {
mid++;
} else {
swap(nums[mid], nums[high]);
high--;
}
}
}
};
9.69MB, 4ms
Javascript
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function(nums) {
let low = 0; // Pointer for 0s (red)
let mid = 0; // Pointer for 1s (white)
let high = nums.length - 1; // Pointer for 2s (blue)
while (mid <= high) {
if (nums[mid] === 0) {
// Swap nums[low] and nums[mid]
[nums[low], nums[mid]] = [nums[mid], nums[low]];
low++;
mid++;
} else if (nums[mid] === 1) {
// No action needed for 1s, just move mid pointer
mid++;
} else {
// nums[mid] === 2, swap nums[mid] and nums[high]
[nums[mid], nums[high]] = [nums[high], nums[mid]];
high--;
// Don't increment mid here because after swap, nums[mid] might need further action
}
}
};
49.19MB, 55ms
