三色球排序的问题,相同的球放到一起,让你按顺序输出红白蓝三种颜色的球,可以用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

相关文章

MySQL中删除重复数据SQL的三种写法

《MySQL中删除重复数据SQL的三种写法》:本文主要介绍MySQL中删除重复数据SQL的三种写法,文中通过代码示例讲解的非常详细,对大家的学习或工作有一定的帮助,需要的朋友可以参考下... 目录方法一:使用 left join + 子查询删除重复数据(推荐)方法二:创建临时表(需分多步执行,逻辑清晰,但会

Redis连接失败:客户端IP不在白名单中的问题分析与解决方案

《Redis连接失败:客户端IP不在白名单中的问题分析与解决方案》在现代分布式系统中,Redis作为一种高性能的内存数据库,被广泛应用于缓存、消息队列、会话存储等场景,然而,在实际使用过程中,我们可能... 目录一、问题背景二、错误分析1. 错误信息解读2. 根本原因三、解决方案1. 将客户端IP添加到Re

详谈redis跟数据库的数据同步问题

《详谈redis跟数据库的数据同步问题》文章讨论了在Redis和数据库数据一致性问题上的解决方案,主要比较了先更新Redis缓存再更新数据库和先更新数据库再更新Redis缓存两种方案,文章指出,删除R... 目录一、Redis 数据库数据一致性的解决方案1.1、更新Redis缓存、删除Redis缓存的区别二

oracle数据库索引失效的问题及解决

《oracle数据库索引失效的问题及解决》本文总结了在Oracle数据库中索引失效的一些常见场景,包括使用isnull、isnotnull、!=、、、函数处理、like前置%查询以及范围索引和等值索引... 目录oracle数据库索引失效问题场景环境索引失效情况及验证结论一结论二结论三结论四结论五总结ora

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2

element-ui下拉输入框+resetFields无法回显的问题解决

《element-ui下拉输入框+resetFields无法回显的问题解决》本文主要介绍了在使用ElementUI的下拉输入框时,点击重置按钮后输入框无法回显数据的问题,具有一定的参考价值,感兴趣的... 目录描述原因问题重现解决方案方法一方法二总结描述第一次进入页面,不做任何操作,点击重置按钮,再进行下

解决mybatis-plus-boot-starter与mybatis-spring-boot-starter的错误问题

《解决mybatis-plus-boot-starter与mybatis-spring-boot-starter的错误问题》本文主要讲述了在使用MyBatis和MyBatis-Plus时遇到的绑定异常... 目录myBATis-plus-boot-starpythonter与mybatis-spring-b

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,:本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一:“杨辉三角”题目链接二:题解代码:三:题解思路:总结一:“杨辉三角”题目链接题目链接:点击这里

mysql主从及遇到的问题解决

《mysql主从及遇到的问题解决》本文详细介绍了如何使用Docker配置MySQL主从复制,首先创建了两个文件夹并分别配置了`my.cnf`文件,通过执行脚本启动容器并配置好主从关系,文中还提到了一些... 目录mysql主从及遇到问题解决遇到的问题说明总结mysql主从及遇到问题解决1.基于mysql