本文主要是介绍算法之路_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、荷兰国旗问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
