- Time O(n), Space O(n)
class Solution {
public:
void sortColors(vector<int>& nums) {
int r = 0, w = 0, b = 0;
for(int i: nums) {
if(i == 0) r++;
else if (i == 1) w++;
else b++;
}
vector<int> sorted;
for(int i = 0; i < r; i++) {
sorted.push_back(0);
}
for(int i = 0; i < w; i++) {
sorted.push_back(1);
}
for(int i = 0; i < b; i++) {
sorted.push_back(2);
}
nums.swap(sorted);
}
};
- O(n) O(1)
class Solution {
public:
void sortColors(vector<int>& nums) {
if(nums.size() <= 1) return;
int r = 0, w = 0, b = nums.size()-1;
while(w <= b) {
if(nums[w] == 0) {
nums[w] = nums[r];
nums[r] = 0;
w++;
r++;
} else if(nums[w] == 1) {
w++;
} else {
nums[w] = nums[b];
nums[b] = 2;
b--;
}
}
}
};
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
