算法之路_9、荷兰国旗问题

2023-12-17 11:18

本文主要是介绍算法之路_9、荷兰国旗问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、荷兰国旗问题(数组分割问题的扩展)

 给定一个数组arr,和一个数num,请把小于num的数放在数组的 左边,等于num的数放在数组的中间,大于num的数放在数组的 右边。

要求额外空间复杂度O(1),时间复杂度O(N)

二、解释

通过具体问题可以看出,这是上一篇博文数组分割问题的扩展,上一篇是将小于等于的放在数组左边,大于放在数组右边,两份切。本篇荷兰国旗问题是小于数放左边,等于放中间,大于放右边,三份切。大家只要上一篇博文的代码理解了,本篇应该问题不大。代码上有些细节解释放在注释中。

三、代码

package algorithm_02;import logarithmic_device.Sort_logarithmic_device;/***荷兰国旗问题    三份切*给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,*等于num的数放在数组的中间,大于num的数放在数组的右边。*/
public class NetherlandsFlag {public static void netherlandsFlag(int arr[],int num){if (arr==null||arr.length<2) {return;}netherlandsFlag(arr,0,arr.length-1,num);}public static void netherlandsFlag(int[] arr, int L, int R,int num) {int less=L-1;//限定比比较元素小的元素范围int more=R+1;//限定比比较元素大的元素范围while (L<more) {if (arr[L]<num) {//若当前元素比比较元素小   //则将当前元素与小元素范围指针得下一个元素交换 并且将小元素范围扩大Sort_logarithmic_device.swap(arr, ++less,L++);}else if(arr[L]>num){//若当前元素比比较元素大  //则将当前元素与大元素范围指针得前一个元素交换 并且将大元素范围扩大Sort_logarithmic_device.swap(arr, L, --more);}else{//若数组元素与待比较元素相等 则将当前元素右移 大范围与小范围不变。确保相等元素在中间L++;}}}public static void main(String[] args) {int arr[]={1,5,4,3,2,8,6,3,0};netherlandsFlag(arr, 3);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+"  ");}}
}

 

这篇关于算法之路_9、荷兰国旗问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

linux生产者,消费者问题

pthread_cond_wait() :用于阻塞当前线程,等待别的线程使用pthread_cond_signal()或pthread_cond_broadcast来唤醒它。 pthread_cond_wait() 必须与pthread_mutex 配套使用。pthread_cond_wait()函数一进入wait状态就会自动release mutex。当其他线程通过pthread

问题:第一次世界大战的起止时间是 #其他#学习方法#微信

问题:第一次世界大战的起止时间是 A.1913 ~1918 年 B.1913 ~1918 年 C.1914 ~1918 年 D.1914 ~1919 年 参考答案如图所示

2024.6.24 IDEA中文乱码问题(服务器 控制台 TOMcat)实测已解决

1.问题产生原因: 1.文件编码不一致:如果文件的编码方式与IDEA设置的编码方式不一致,就会产生乱码。确保文件和IDEA使用相同的编码,通常是UTF-8。2.IDEA设置问题:检查IDEA的全局编码设置和项目编码设置是否正确。3.终端或控制台编码问题:如果你在终端或控制台看到乱码,可能是终端的编码设置问题。确保终端使用的是支持你的文件的编码方式。 2.解决方案: 1.File -> S

vcpkg安装opencv中的特殊问题记录(无法找到opencv_corexd.dll)

我是按照网上的vcpkg安装opencv方法进行的(比如这篇:从0开始在visual studio上安装opencv(超详细,针对小白)),但是中间出现了一些别人没有遇到的问题,虽然原因没有找到,但是本人给出一些暂时的解决办法: 问题1: 我在安装库命令行使用的是 .\vcpkg.exe install opencv 我的电脑是x64,vcpkg在这条命令后默认下载的也是opencv2:x6

问题-windows-VPN不正确关闭导致网页打不开

为什么会发生这类事情呢? 主要原因是关机之前vpn没有关掉导致的。 至于为什么没关掉vpn会导致网页打不开,我猜测是因为vpn建立的链接没被更改。 正确关掉vpn的时候,会把ip链接断掉,如果你不正确关掉,ip链接没有断掉,此时你vpn又是没启动的,没有域名解析,所以就打不开网站。 你可以在打不开网页的时候,把vpn打开,你会发现网络又可以登录了。 方法一 注意:方法一虽然方便,但是可能会有

代码随想录算法训练营:12/60

非科班学习算法day12 | LeetCode150:逆波兰表达式 ,Leetcode239: 滑动窗口最大值  目录 介绍 一、基础概念补充: 1.c++字符串转为数字 1. std::stoi, std::stol, std::stoll, std::stoul, std::stoull(最常用) 2. std::stringstream 3. std::atoi, std

人工智能机器学习算法总结神经网络算法(前向及反向传播)

1.定义,意义和优缺点 定义: 神经网络算法是一种模仿人类大脑神经元之间连接方式的机器学习算法。通过多层神经元的组合和激活函数的非线性转换,神经网络能够学习数据的特征和模式,实现对复杂数据的建模和预测。(我们可以借助人类的神经元模型来更好的帮助我们理解该算法的本质,不过这里需要说明的是,虽然名字是神经网络,并且结构等等也是借鉴了神经网络,但其原型以及算法本质上还和生物层面的神经网络运行原理存在

vue同页面多路由懒加载-及可能存在问题的解决方式

先上图,再解释 图一是多路由页面,图二是路由文件。从图一可以看出每个router-view对应的name都不一样。从图二可以看出层路由对应的组件加载方式要跟图一中的name相对应,并且图二的路由层在跟图一对应的页面中要加上components层,多一个s结尾,里面的的方法名就是图一路由的name值,里面还可以照样用懒加载的方式。 页面上其他的路由在路由文件中也跟图二是一样的写法。 附送可能存在

vue+elementui--$message提示框被dialog遮罩层挡住问题解决

最近碰到一个先执行this.$message提示内容,然后接着弹出dialog带遮罩层弹框。那么问题来了,message提示框会默认被dialog遮罩层挡住,现在就是要解决这个问题。 由于都是弹框,问题肯定是出在z-index比重问题。由于用$message方式是写在js中而不是写在html中所以不是很好直接去改样式。 不过好在message组件中提供了customClass 属性,我们可以利用

Visual Studio中,MSBUild版本问题

假如项目规定了MSBUild版本,那么在安装完Visual Studio后,假如带的MSBUild版本与项目要求的版本不符合要求,那么可以把需要的MSBUild添加到系统中,然后即可使用。步骤如下:            假如项目需要使用V12的MSBUild,而安装的Visual Studio带的MSBUild版本为V14。 ①到MSDN下载V12 MSBUild包,把V12包解压到目录(