# 荷兰国旗问题 ## 小于等于放左边，大于放右边 首先我们来看问题1： 给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。 要求额外空间复杂度O(1)，时间复杂度O(N)。  ### 代码实现 ~~~ public static void main(String[] args) { int[] arr = {3,6,2,4,8}; partition1(arr,4); System.out.println(Arrays.toString(arr)); } /** * 问题1： * 给定一个数组arr，和一个数num，请把小于等于于num的数放在数组的左边，大于num的数放在数组的右边。 * 要求额外空间复杂度O(1)，时间复杂度O(N)。 */ public static void partition1(int[] arr,int num){ // left表示左侧区域,i是遍历指针 int left = -1; int i = 0; while (i < arr.length){ if(arr[i] <= num){ // 交换指针位置和小于区域下一个位置，小于区域和指针右移 swap(arr,++left,i++); }else{ i++; // 大于num，指针右移 } } } // 异或交换 private static void swap(int[] arr,int i,int j){ if(i == j){ return; } arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } ~~~ ``` 程序输出： [3, 2, 4, 6, 8] ``` ## 荷兰国旗问题 ***小于放左边，等于放中间，大于放右边*** 给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。 要求额外空间复杂度O(1)，时间复杂度O(N)。  ### 代码实现 ~~~ public static void main(String[] args) { int[] arr = {3,6,2,4,8,1,4}; partition2(arr,4); System.out.println(Arrays.toString(arr)); } public static void partition2(int[] arr,int num){ // left表示左侧区域,i是遍历指针 int left = -1; int right = arr.length; int i = 0; while (i < right){ if(arr[i] < num){ // 小于当前数的，交换指针位置和小于区域下一个位置，小于区域和指针右移 swap(arr,++left,i++); }else if(arr[i] == num){ i++; // 等于num，指针右移 }else{ // 大于当前数的，指针和大于区域前一位交换，大于区域左移 swap(arr,--right,i); } } } // 异或交换 private static void swap(int[] arr,int i,int j){ if(i == j){ return; } arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } ~~~ ``` [3, 2, 1, 4, 4, 8, 6] ```