荷兰国旗问题
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
