HappyCpp

一个不会打代码的程序猿

0%

荷兰国旗问题

荷兰国旗问题

荷兰国旗问题

荷兰国旗是由红白蓝3种颜色的条纹拼接而成,如下图所示:

如果这样的条纹有多个,但是仍由这3种颜色组成,且各种颜色数量不一,并且随机组成了一个新的图形,新的图形的情况之一如下图所示:

现在给定一个包含红色、白色和蓝色,一共n个小球,原地对它们进行排序,使得小球按照红色、白色、蓝色顺序排列。这里我们用0、1、2分别代表红白蓝三种颜色。
这其实是快速排序的另一种解决问题的方法。

我们可以将整个数组分成三段,分别为0,1,2,那么我们怎么实现呢?我们定义三个指针,l=-1,r=n,cur=0;l指向最后一个为0的元素,r为第一个为2的元素,cur指针指向当前元素,我们整个数组的循环条件是cur< r (如果是l< r会造成死循环)。

如果cur指向元素等于1,cur指针后移即可,如果等于0,交换a[cur]和a[l]的后一个元素相当于我们把a[cur]放到l+1位置,然后cur指针后移;如果cur指向元素等于2,交换[cur]和a[r]的前一个元素相当于我们把a[cur]放到r-1位置,这里要注意的是,我们cur指针不能后移,因为此时cur位置的元素还没有被检查,是之前r-1位置的元素。这样就可以将元素排好序。

附代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[105];
int main() {
int n;
scanf("%d",&n);
for(int i=0; i<n; i++) {
scanf("%d",&a[i]);
}
int l=-1,r=n,cur=0;
while(cur<r) {
if(a[cur]==1)
cur++;
else if(a[cur]==0) {
swap(a[cur],a[++l]);
cur++;
} else if(a[cur]==2)
swap(a[cur],a[--r]);
}
for(int i=0; i<n; i++) {
printf("%d ",a[i]);
}
printf("\n");
return 0;
}

附题目链接:https://leetcode-cn.com/problems/sort-colors/