Sort Colors
Given an array withnobjects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.
click to show follow up.
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 an one-pass algorithm using only constant space?
科学思维: 这道题带点
QuikSort思想,
不过不如说是分窗口处理数据的思想,好像更贴切:O(∩_∩)O~
1 red窗口
2 white窗口
3 blue窗口
4 未处理窗口
算法一:下面是分三个指标,都指向各个颜色球的末位,这个算法的好处是可以很容易修改成分4个,5个颜色块的算法,当然如果颜色块继续增多,那么最好还是使用counting sort算法了,下面也给出了程序。
class Solution {
public:
void sortColors(int A[], int n)
{
int r = 0, r_w = 0, w_b = 0;
for (int i = 0; i < n; i++)
{
switch (A[i])
{
case 0:
{
swap(A[i], A[r]);
if (r_w != 0)
{
swap(A[i], A[r + r_w]);
}
if (w_b != 0)
{
swap(A[i], A[r + r_w + w_b]);
//w_b++;这个颜色球并没有增加,所以不需要++
}
//注意:数值会变动,需要保存好,很容易忽略的。
r++;
}
break;
case 1:
{
swap(A[i], A[r + r_w]);
if (w_b != 0)
{
swap(A[i], A[r + r_w + w_b]);
}
//注意:数值会变动,需要保存好,太容易忽略了。
r_w++;
}
break;
case 2:
w_b++;
}
}
}
};
算法二:利用三个分块的特性,分为前一块,后一块,中间一块,这样更加好处理,程序也简洁很多:
class Solution {
public:
void sortColors(int A[], int n)
{
int r = 0, w = 0, b = n-1;
for (int w = 0; w <= b; )
{
switch (A[w])
{
case 0:
swap(A[r++], A[w++]);
break;
case 1:
w++;
break;
case 2:
swap(A[w], A[b--]);
}
}
}
};
算法三:Counting Sort算法,这是个通用的算法的了,非常常用。不过要使用额外空间O(n),想了很久,感觉好像不能不使用额外空间,不过可以优化一点,算法四给出程序。
void sortColors5(int A[], int n)
{
int countArray[NUM_OF_COLORS+1] = {0};
for (int i = 0; i < n; i++)
{
countArray[A[i]+1]++;
}
for (int i = 2; i <= NUM_OF_COLORS; i++)
{
countArray[i] += countArray[i-1];
}
vector<int> B(A, A+n);
for (int i = 0; i < n; i++)
{
B[countArray[A[i]]++] = A[i];
}
for (int i = 0; i < n; i++)
{
A[i] = B[i];
}
}
算法四:优化counting sort,设关键字为m(本题的关键字为3)一般都比数列n长度小很多,如果使用额外空间O(m),那么就可以节省很多空间。如下面程序处理一下就可以做到了。
const static int NUM_OF_COLORS = 3;
void sortColors4(int A[], int n)
{
int countArray[NUM_OF_COLORS+1] = {0};
for (int i = 0; i < n; i++)
{
countArray[A[i]+1]++;
}
for (int i = 2; i <= NUM_OF_COLORS; i++)
{
countArray[i] += countArray[i-1];
}
vector<int> fixedCount(countArray, countArray+NUM_OF_COLORS+1);
int j = 0;
for (int i = 0; i < n;)
{
if (A[i] != j) swap(A[i], A[countArray[A[i]]++]);
else
{
countArray[j]++;
i++;
}
while (i<n && j<=NUM_OF_COLORS && i == fixedCount[j+1])
{
j++;
i = countArray[j];
}
}
}
//2014-2-11 update
void sortColors(int A[], int n)
{
int red = 0, white = 0, blue = n-1;
while (white<=blue)
{
if (A[white] == 0) swap(A[red++], A[white++]);
else if (A[white] == 1) white++;
else swap(A[white], A[blue--]);
}
}
分享到:
相关推荐
算法 Leetcode刷题手册 labuladong的算法小抄官方完整版
基于java的leetcode刷题与复习指南算法模板代码
leetcode题目精选,JAVA算法刷题,算法题leetcode题目精选,JAVA算法刷题,算法题leetcode题目精选,JAVA算法刷题,算法题leetcode题目精选,JAVA算法刷题,算法题leetcode题目精选,JAVA算法刷题,算法题leetcode...
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
用来记录我们刷LeetCode题目时候的心酸历史。我们保证,这些代码一定通过了当时LeetCode的测试,虽然后续可能因为LeetCode测试条件的改变导致某些解题无法通过,但我们会实时的跟进。 编程语言使用Golang,代码风格...
leetcode常见的100热点算法题 的算法者得offer
LeetCode刷题手册,刷算法题必备
Java算法刷题带注释Leetcode,基础算法
LeetCode算法刷题
leetcode常用算法java代码
leetcode初级算法代码C++完整版,里面是我认为最适合于新手解题的代码,包含详细的注释,还有个人感悟和总结,适合于想要入门的新手。
C语言 C语言 LeetCode算法刷题30天全面提升教程算法刷题30天全面提升教程
算法:Leetcode剑指报价经典算法题型
2020高频面试算法整理 leetcode ,18个大类,80+到常见算法题。 1.热身题|1)查找唯一数字|2)查找N/2数字|3)判断数字是否存在|4)合并二叉树|5)泡鸡蛋问题|2.互联网公司最常见的面试算法题有哪些?|3.TOP INTERVIEW ...
算法相关知识储备 LeetCode with Python
珍藏好书,大神笔记 本文档为数据结构和算法学习笔记,我们希望这个笔记能给你在学习算法的过程提供思路和源码方面的参考,但绝不鼓励死记硬背!全文大致分为以下三大部分: