三色球排序的问题,相同的球放到一起,让你按顺序输出红白蓝三种颜色的球,可以用012来表示,要求只能扫描一次数组

本文主要是介绍三色球排序的问题,相同的球放到一起,让你按顺序输出红白蓝三种颜色的球,可以用012来表示,要求只能扫描一次数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!



    问题描述:
我们将乱序的红白蓝三色小球排列成有序的红白蓝三色的同颜色在一起的小球组。这个问题之所以叫荷兰国旗,是因为我们可以将红白蓝三色小球想象成条状物,有序排列后正好组成荷兰国旗。如下图所示:

   

    这个问题,类似快排中partition过程。不过,要用三个指针,一前begin,一中current,一后end,俩俩交换。

  初始化:begin = current = 0; end = n-1;然后使begin指向开头处第一个不为0的位置,end指向后面第一个不为2的位置。

 即:

    while (arr[begin] == 0)

             begin++;

    current = begin + 1;

    while (arr[end] == 2)

               end--;

初始化好之后,进行下面操作。

1、current遍历,整个数组序列,arr[current] == 1,则current++,
2、arr[current] == 0,则与arr[begin]交换,而后current++,begin++,
3、arr[current] == 2,则与arr[end]交换,而后,current不动,end--。(之所以current不动,是因为交换后,arr[current]可能为0,此时要和arr[begin]互换的)


代码主体:

while( current<=end )      
{           if( array[current] ==0 )           {               swap(array[current],array[begin]);                current++;                begin++;          }           else if( array[current] == 1 )          {               current++;          } else //When array[current] =2 {             swap(array[current],array[end]);              end--;          }    
}//end while

这篇关于三色球排序的问题,相同的球放到一起,让你按顺序输出红白蓝三种颜色的球,可以用012来表示,要求只能扫描一次数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/204373

相关文章

使用Python和OpenCV库实现实时颜色识别系统

《使用Python和OpenCV库实现实时颜色识别系统》:本文主要介绍使用Python和OpenCV库实现的实时颜色识别系统,这个系统能够通过摄像头捕捉视频流,并在视频中指定区域内识别主要颜色(红... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间详解

OpenCV实现实时颜色检测的示例

《OpenCV实现实时颜色检测的示例》本文主要介绍了OpenCV实现实时颜色检测的示例,通过HSV色彩空间转换和色调范围判断实现红黄绿蓝颜色检测,包含视频捕捉、区域标记、颜色分析等功能,具有一定的参考... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间

苹果macOS 26 Tahoe主题功能大升级:可定制图标/高亮文本/文件夹颜色

《苹果macOS26Tahoe主题功能大升级:可定制图标/高亮文本/文件夹颜色》在整体系统设计方面,macOS26采用了全新的玻璃质感视觉风格,应用于Dock栏、应用图标以及桌面小部件等多个界面... 科技媒体 MACRumors 昨日(6 月 13 日)发布博文,报道称在 macOS 26 Tahoe 中

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

MySQL 设置AUTO_INCREMENT 无效的问题解决

《MySQL设置AUTO_INCREMENT无效的问题解决》本文主要介绍了MySQL设置AUTO_INCREMENT无效的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参... 目录快速设置mysql的auto_increment参数一、修改 AUTO_INCREMENT 的值。

关于跨域无效的问题及解决(java后端方案)

《关于跨域无效的问题及解决(java后端方案)》:本文主要介绍关于跨域无效的问题及解决(java后端方案),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录通用后端跨域方法1、@CrossOrigin 注解2、springboot2.0 实现WebMvcConfig

Go语言中泄漏缓冲区的问题解决

《Go语言中泄漏缓冲区的问题解决》缓冲区是一种常见的数据结构,常被用于在不同的并发单元之间传递数据,然而,若缓冲区使用不当,就可能引发泄漏缓冲区问题,本文就来介绍一下问题的解决,感兴趣的可以了解一下... 目录引言泄漏缓冲区的基本概念代码示例:泄漏缓冲区的产生项目场景:Web 服务器中的请求缓冲场景描述代码

Java死锁问题解决方案及示例详解

《Java死锁问题解决方案及示例详解》死锁是指两个或多个线程因争夺资源而相互等待,导致所有线程都无法继续执行的一种状态,本文给大家详细介绍了Java死锁问题解决方案详解及实践样例,需要的朋友可以参考下... 目录1、简述死锁的四个必要条件:2、死锁示例代码3、如何检测死锁?3.1 使用 jstack3.2

解决JSONField、JsonProperty不生效的问题

《解决JSONField、JsonProperty不生效的问题》:本文主要介绍解决JSONField、JsonProperty不生效的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录jsONField、JsonProperty不生效javascript问题排查总结JSONField

github打不开的问题分析及解决

《github打不开的问题分析及解决》:本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三