# 荷蘭國旗問題 ## 小于等于放左邊，大于放右邊 首先我們來看問題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] ```