LeetCode 75 颜色分类
🟡 中等 https://leetcode.cn/problems/sort-colors/description/
last数组
思路：维护last数组记录 0 1 2 的上次位置，对于1首先检查last[1] 为-1的话就再检查 last[0] 的值；对于数字num，依次向前检查last[num] last[num-1] ，如果都是 -1 就返回-1。
每次找到last位置后交换，交换完还要继续检查交换后的当前位置的值是否在对应的last位置后面。
内层while 循环至多执行两次，总共O(n)。
class Solution {
public:
int should_index(vector<int>& nums,int num){
for(int i = num;i>=0;i--){
if(nums[i]!=-1) return nums[i];
}
return -1;
}
void sortColors(vector<int>& nums) {
vector<int> last(3,-1);
for(int i = 0;i<nums.size();i++){
int last_index = should_index(last,nums[i]);
while(last_index+1!=i){
last[nums[i]] = last_index+1;
swap(nums[i],nums[last_index+1]);
last_index = should_index(last,nums[i]);
}
last[nums[i]] = last_index+1;
}
}
};
经典双指针
在 nums[i]==0 时为什么要 i++，因为：为0时交换过来的是 0或1，所以要i++，当nums[i] = 2时不用i++，因为交换过来的可能为 0 1 2 要继续判断。
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int p0 = 0;
int p2 = n - 1;
int i = 0;
while(i<=p2){
if(nums[i]==0){
swap(nums[i],nums[p0]);
p0++;
i++;
}else if(nums[i]==2){
swap(nums[i],nums[p2]);
p2--;
}else{
i++;
}
}
}
};
或者自己写的好理解版本
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int p0 = 0;
int p2 = n - 1;
for (int i = 0; i < n; i++) {
while(i<=p2){
if(nums[i]==1) break;
if(nums[i]==0){
if(i==p0) break;
swap(nums[i],nums[p0]);
p0++;
}
if(nums[i]==2){
if(i==p2) break;
swap(nums[i],nums[p2]);
p2--;
}
}
}
}
};
或者
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int p0 = 0;
int p2 = n - 1;
int i = 0;
while(i<=p2){
if(nums[i]==0){
if(nums[p0]==0){
i++;
p0++;
continue;
}
swap(nums[i],nums[p0]);
p0++;
// i++;
}else if(nums[i]==2){
swap(nums[i],nums[p2]);
p2--;
}else{
i++;
}
}
}
};
刷油漆
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int n0 = 0;
int n1 = 0;
int i = 0;
while(i<n){
int num = nums[i];
nums[i] = 2;
if(num<2){
nums[n1]=1;
n1++;
}
if(num<1){
nums[n0] = 0;
n0++;
}
i++;
}
}
};