荷兰国旗问题
给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间,大于num的数放在数组的右边。
要求额外空间复杂度O(1),时间复杂度O(N)
import java.util.Arrays; /** * @author sky *给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间,大于num的数放在数组的右边。 *要求额外空间复杂度O(1),时间复杂度O(N) */ public class 荷兰国旗问题 { //算法核心代码: public static int[] partition(int[] a,int l,int r,int num) { int less = l - 1; int more = r + 1; int cur = l; while(cur < more) { if(a[cur] < num) { swap(a,++less,cur++); }else if(a[cur] > num) { swap(a,--more,cur); }else { cur++; } } return new int [] {less+1,more-1}; } //交换代码 private static void swap(int[] a, int less, int cur) { int temp = a[less]; a[less] = a[cur]; a[cur] = temp; } public static int[] generateArray() { int[] arr = new int[10]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) (Math.random() * 3); } return arr; } public static void main(String[] args) { int[] test = generateArray();//产生一个随机数组 System.out.println(Arrays.toString(test));//打印数组 int[] res = partition(test, 0, test.length - 1, 1);//数组,起始位置,终止位置 System.out.println(Arrays.toString(test)); System.out.println(res[0]);//返回的是等于num的数组的起始位置和终止位置 System.out.println(res[1]); } }