Code15 荷兰国旗问题

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

解决该问题，只需先设定三个用于指定元素的下标指针（PS：在Java中没有指针，此处方便描述）:一个前指针begin，一个中指针current，一个后指针end。Current指针遍历整个数组序列：

（1）当current指针所指元素为0时，与begin指针所指的元素交换，而后current++，begin++；
（2）当current指针所指元素为1时，不做任何交换，而后current++；
（3）当current指针所指元素为2时，与end指针所指的元素交换，而后current指针不动，end–.

荷兰国旗问题：给定一个数组 arr和一个数num, 请把小于num的数放在数组的坐标，等于num的数放到中间，大于num的数放到右边

public static void partion(int []arr ,int L,int R,int num){int less = L - 1;int more = R + 1;int index = L;while (less < more){if(arr[index] < num){swap(arr,++less,index++);}else if(arr[index] == num){index ++;}else {swap(arr,index,--more);}} }public static void swap(int [] arr ,int i ,int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

荷兰国旗变种，以数组最后一个值作为划分值来分成3个不同部分

//arr[L....R]玩荷兰国旗问题，以arr[R]作划分值//也就是 <arr[R]   =arr[R]     >arr[R]//返回等于arr[R]数组下标两个值public static int[] netherlandsFlag(int[] arr,int L,int R){if(L > R){return new int[]{-1,-1};}if(L == R){return new int[]{L,R};}int less = L-1;int more = R;//提前把最后一个数摘出去，最后处理，因为要做划分值int index = L;while (index < more){if(arr[index] < arr[R]){swap(arr,++less,index++);
//                swap(arr,less+1,index);
//                less++;
//                index++;}else if(arr[index] == arr[R]){index ++;}else{swap(arr,index,--more);
//                swap(arr,index,more-1);
//                more--;}}swap(arr,more,R);//把arr[R]作为划分值得交换到等于区return new int[]{less+1,more};}public static void swap(int [] arr ,int i ,int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}