189 8069 5689
这篇文章主要介绍了C++怎么实现颜色排序的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇C++怎么实现颜色排序文章都会有所收获，下面我们一起来看看吧。
翔安网站建设公司成都创新互联公司,翔安网站设计制作，有大型网站制作公司丰富经验。已为翔安成百上千提供企业网站建设服务。企业网站搭建\外贸网站制作要多少钱，请找那个售后服务好的翔安做网站的公司定做！
Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0"s, 1"s, and 2"s, then overwrite array with total number of 0"s, then 1"s and followed by 2"s.
Could you come up with a one-pass algorithm using only constant space?
这道题的本质还是一道排序的题，题目中给出提示说可以用计数排序，需要遍历数组两遍，那么先来看这种方法，因为数组中只有三个不同的元素，所以实现起来很容易。
- 首先遍历一遍原数组，分别记录 0，1，2 的个数。
- 然后更新原数组，按个数分别赋上 0，1，2。
解法一：
class Solution {
public:
void sortColors(vector& nums) {
vector colors(3);
for (int num : nums) ++colors[num];
for (int i = 0, cur = 0; i < 3; ++i) {
for (int j = 0; j < colors[i]; ++j) {
nums[cur++] = i;
}
}
}
}; 题目中还要让只遍历一次数组来求解，那么就需要用双指针来做，分别从原数组的首尾往中心移动。
- 定义 red 指针指向开头位置，blue 指针指向末尾位置。
- 从头开始遍历原数组，如果遇到0，则交换该值和 red 指针指向的值，并将 red 指针后移一位。若遇到2，则交换该值和 blue 指针指向的值，并将 blue 指针前移一位。若遇到1，则继续遍历。
解法二：
class Solution {
public:
void sortColors(vector& nums) {
int red = 0, blue = (int)nums.size() - 1;
for (int i = 0; i <= blue; ++i) {
if (nums[i] == 0) {
swap(nums[i], nums[red++]);
} else if (nums[i] == 2) {
swap(nums[i--], nums[blue--]);
}
}
}
}; 当然我们也可以使用 while 循环的方式来写，那么就需要一个变量 cur 来记录当前遍历到的位置，参见代码如下：
解法三：
class Solution {
public:
void sortColors(vector& nums) {
int left = 0, right = (int)nums.size() - 1, cur = 0;
while (cur <= right) {
if (nums[cur] == 0) {
swap(nums[cur++], nums[left++]);
} else if (nums[cur] == 2) {
swap(nums[cur], nums[right--]);
} else {
++cur;
}
}
}
}; 关于“C++怎么实现颜色排序”这篇文章的内容就介绍到这里，感谢各位的阅读！相信大家对“C++怎么实现颜色排序”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注创新互联行业资讯频道。