D8 全排列(非回溯法)

全排列原題鏈接

在刷leetcode的時候，看到這道題目并沒法使用像STL的next_permutation方法，感嘆C++便利的同時，又惋惜Java并沒有類似的API，那我們只能從原理入手了，仿寫此算法。

其實回溯法更應該掌握，因為擴展性高，我們學知識本來就是舉一反三的，如果這個算法只適用于這道題，那我們深入學習的必要性就沒那么大了。

我們來看實現過程：

1. 找到「下降點」i

• 從右向左掃描數組，找到第一個 arr[i] < arr[i+1] 的位置 i。
• 為什么要找這個？因為字典序的排列從右向左最長的非遞增序列是當前排列的尾部，我們想找到可以“升高”的那個位置。

說人話就是，這里非遞增序列我們先理解為遞減序列（其實還包括前后相等），其實是找遞減序列的入口，為什么呢？

因為按照字典序來看，這一部分是不便于排列的，因為難以升高，我們得優先換這部分的前一部分。

如果還是不理解，可以繼續往后看，看到后面就會明白這里為什么找下降點。

舉例：
arr = [1, 3, 5, 4, 2]
從右往左，觀察 arr[i] >= arr[i+1]：

• 4 >= 2 → 是
• 5 >= 4 → 是
• 3 >= 5 → 否，3 < 5
  所以 i = 1（對應數字 3）。
• 如果 i < 0，說明整個數組是非遞增序列（即當前排列是最大字典序），沒有下一個排列，函數返回 false。

2. 找到交換點 j

• 從右向左找到第一個 arr[j] > arr[i] 的位置。
• 在 arr[i] 后面的序列中找一個比 arr[i] 大的最小數字交換，使排列字典序剛好變大一點。

繼續上例：
i=1，arr[i]=3
從右往左找第一個比 3 大的元素：

• 2 <= 3 不符合
• 4 > 3 符合，且是最右邊的符合條件元素
  所以 j = 3。

3. 交換 arr[i] 和 arr[j]

交換 3 和 4，變成：

[1, 4, 5, 3, 2]

4. 反轉 i+1 位置到數組末尾的部分

將 i+1 到末尾的子數組反轉（升序排列），保證新排列是字典序中「緊接著」的下一排列。

這里 i+1=2，子數組是 [5, 3, 2]，反轉后是 [2, 3, 5]，數組變成：

[1, 4, 2, 3, 5]

這個就是字典序的下一個排列。

既然這樣，那么我們需要實現兩個函數swap和reverse

class Solution {public List<List<Integer>> permute(int[] nums) {Arrays.sort(nums); //這段代碼用于判斷List<List<Integer>> ans = new ArrayList<>();do{List<Integer> temp = new ArrayList<>();for (int num : nums) {temp.add(num);}ans.add(temp);}while(nextPermutation(nums));return ans;}private static boolean nextPermutation(int[] arr){int i = arr.length - 2;while(i >= 0 && arr[i] >= arr[i + 1]) i--; //找到下降點if(i < 0) return false;int j = arr.length - 1;while(arr[j] <= arr[i]) j--; //找出比下降點大的swap(arr, i, j);reverse(arr, i + 1, arr.length - 1);return true;}private static void swap(int[] arr, int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}private static void reverse(int arr[], int l, int r){while(l < r) swap(arr, l++, r--);}
}

如果這篇文章對你有幫助，請點贊評論收藏，創作不易，你的支持是我堅持的動力。