题解 | #颜色分类#
颜色分类
http://www.nowcoder.com/practice/52e04ddb7b5640a8869c2d3da2ad3344
题意：
给定一个包含红色，白色，蓝色，一同 n 个元素的数组，对其进行排序使得相同的颜色相邻并且按照 红色，白色，蓝色的顺序排序。
数组中 0 代表红色，1 代表白色，2 代表蓝色。
方法一：
快排
思路：根据题意可知，数值的顺序要从小到大，因此快排即可。
class Solution {
public:
vector<int> sortColor(vector<int>& colors) {
sort(colors.begin(),colors.end());//排序
return colors;
}
};
时间复杂度：%2C%E5%BF%AB%E6%8E%92%E7%9A%84%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E3%80%82)
空间复杂度：%2C%E5%B8%B8%E6%95%B0%E7%BA%A7%E5%88%AB%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
方法二：
计数排序
思路：首先，遍历数组对值计数统计（计数排序）；
之后，再次遍历数组，用新值覆盖原值。
class Solution {
public:
int cnt[5]={0};
vector<int> sortColor(vector<int>& colors) {
int n=colors.size();
for(int i=0;i<n;i++){//计数排序
cnt[colors[i]]++;
}
int j=0;
for(int i=0;i<n;i++){//遍历数组，用新值覆盖原值
if(cnt[j]==0){
j++;
}
colors[i]=j;
cnt[j]--;
}
return colors;
}
};
时间复杂度：%2C%E9%81%8D%E5%8E%86%E6%95%B0%E7%BB%84%E3%80%82)
空间复杂度：%2C%E8%AE%A1%E6%95%B0%E6%95%B0%E7%BB%84cnt%5B%5C%20%5D%E7%9A%84%E9%95%BF%E5%BA%A6%E4%B8%BA3%EF%BC%8C%E5%B8%B8%E6%95%B0%E7%BA%A7%E5%88%AB%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
查看4道真题和解析