荷兰国旗问题

程序员文章站 2022-03-26 17:42:47

这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能，丰富你的文章UML 图表FLowchart流程图导出与导入导出导入欢迎使用Markdown编辑器你好！这是你第一次使用 Markdown编辑器所展示的欢迎页。如果你想学习如何使用Mar...

荷兰国旗问题

1.问题描述：给定一个数组arr，和一个数num，请把小于num的数放在数组左边，等于
num的数放在数组中间，大于num的数放在数组右边

思路：首先构建三个区域：小于num区域，大于num区域和等于num区域，并相对应的定义三个指针less，curr和more，接着利用curr指针遍历数组，根据数组中的每个数与num比较的结果，来扩展相应的区域，最终curr==more结束。具体描述见下图

2.图解：
荷兰国旗问题

荷兰国旗问题

代码

去博客设置页面，选择一款你喜欢的代码片高亮样式，下面展示同样高亮的 代码片.

import java.util.Arrays;

public class NetherlandsFlag {
	public static void main(String[] args) {
		int [] arr= {3,2,5,8,4,6};
		partition(arr,0,arr.length-1,5);
		System.out.println(Arrays.toString(arr));
	}
	public static void swap(int arr[],int i,int j) {
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
	//返回一个等于num 的值空间
	public static int[] partition(int arr[],int L,int R,int num) { 
		int less =L-1;  //用来交换
		int more=R+1; //相当于有三个指针
		int cur=L; //用来遍历 
		
		while (cur<more) {
			if(arr[cur]<num) {
				swap(arr,++less,cur++);
			}else if(arr[cur]>num) {
				swap(arr,--more,cur);
			}else {
				cur++;
				
			}
		}
		return new int[] {less+1,more-1};
	}
			

}

本文地址：https://blog.csdn.net/qq_30393005/article/details/107890759

荷兰国旗问题