#頭條創作挑戰賽#

  這節學習一下荷蘭旗問題，為學習快排打一個基礎。

  荷蘭旗我還沒見過呢？趕緊搜一下瞅瞅：

  這就是荷蘭旗，三色啊那啥叫荷蘭旗問題呢，來個例子，我有一個數組arr，還有一個數X，數組中所有小于X的放數組左邊，等于X的放數組中間，大于X的放數組右邊，這就是荷蘭旗問題。

  造一個題呗，圖來

  暴力思路來一次

  整理下：

• 有個交換動作，來個swap
• 我需要左邊界L
• 我需要右邊界R
• 考慮邊界L>=R

  話不多說，貼上代碼：

/** * arr[L...R] 玩荷蘭國旗問題的劃分，以arr[R]做劃分值 <arr[R] ==arr[R] > arr[R] * * @param arr 數組 * @param L 左邊界 * @param R 右邊界 * @return 下标範圍 */ public static int[] netherlandsFlag(int[] arr, int L, int R) { if (L > R) { // L...R L>R，不是有效範圍 return new int[] { -1, -1 }; } if (L == R) { return new int[] { L, R }; } // 可以從初始位理解，剛開始的時候，左邊界還沒有右擴，所以less是L-1 int less = L - 1; // < 區 右邊界 int more = R; // > 區 左邊界 int index = L; // 當前數的位置，不能和 右區的左邊界撞上 while (index < more) { if (arr[index] == arr[R]) {// 當前位置的數 和 目标數 相等的時候跳過 index ; } else if (arr[index] < arr[R]) {// 當前位置的數 小于 目标數 // 當前位置的數 和 L 1的數交換，然後位置右移，左邊界右移 swap(arr, index , less); } else { // > // 當前位置的數 和 R-1的數交換，然後位置不變，右邊界左移 swap(arr, index, --more); } } //more是右邊界-1的位置，和R交換 swap(arr, more, R); // <[R] =[R] >[R] //等于區域的第一個數的位置，和等于區域的最後一個數的位置 return new int[] { less 1, more }; }

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!