Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1838369
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2388
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(184)

文章存档

2021年(26)

2020年(56)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: C/C++

2020-12-22 20:10:10

第一次见到这个问题的时候,脑子里面第一反应居然是荷兰豆。。。

好了,言归正传,荷兰国旗就是比较分明的三条颜色,映射到程序员身上就是给定一个数组,以及一个target目标,让你给这个数组排个序,要求分成三段,第一段都小于target,第二段都等于target,第三段都大于target。

第二反应这东西就是快速排序的第一部分,只不过中间有序,这样的话,由于是分了三段,就需要两个指针i, j来记录,在实际遍历数组的时候,是需要另外的一个表示当前遍历结尾的k变量,i,j,和k将整个数组分成四个部分[0,i)已经排序,小于target部分,[i,j)已经排序,等于target部分,[j,k],未排序部分,(k,~)已经排序,大于target部分。这样的话,遍历的起始和终止条件就出现了,i,j起始都为0,k=n-1,终止条件就是j>k,所以代码如下:


点击(此处)折叠或打开

  1. void flag_of_netherland(int *arr, int n, int target){
  2.     int i=0,j=0, k=n-1;
  3.     int temp;
  4.     while(j<=k){
  5.         if(arr[j]<target){
  6.             temp=arr[i];
  7.             arr[i]=arr[j];
  8.             arr[j]=temp;
  9.             i++,j++;
  10.         }else if(arr[j]>target){
  11.             temp=arr[k];
  12.             arr[k]=arr[j];
  13.             arr[j]=temp;
  14.             k--;// 这会不能j++,因为你不知道换过来的是个啥东西
  15.         }else{
  16.             j++;
  17.         }
  18.     }
  19. }

阅读(1618) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~