LeetCode031之下一個排列（相關話題：字典序）

題目描述

實作擷取 下一個排列 的函數，算法需要将給定數字序列重新排列成字典序中下一個更大的排列。

如果不存在下一個更大的排列，則将數字重新排列成最小的排列（即升序排列）。

必須 原地 修改，隻允許使用額外常數空間。

示例 1：

輸入：nums = [1,2,3]

輸出：[1,3,2]

示例 2：

輸入：nums = [3,2,1]

輸出：[1,2,3]

示例 3：

輸入：nums = [1,1,5]

輸出：[1,5,1]

示例 4：

輸入：nums = [1]

輸出：[1]

思路分析

注意到下一個排列總是比目前排列要大，除非該排列已經是最大的排列。我們希望找到一種方法，能夠找到一個大于目前序列的新序列，且變大的幅度盡可能小。具體地：

我們需要将一個左邊的「較小數」與一個右邊的「較大數」交換，以能夠讓目前排列變大，進而得到下一個排列。

同時我們要讓這個「較小數」盡量靠右，而「較大數」盡可能小。當交換完成後，「較大數」右邊的數需要按照升序重新排列。這樣可以在保證新排列大于原來排列的情況下，使變大的幅度盡可能小。

以排列 [4,5,2,6,3,1][4,5,2,6,3,1] 為例：

我們能找到的符合條件的一對「較小數」與「較大數」的組合為 22 與 33，滿足「較小數」盡量靠右，而「較大數」盡可能小。

當我們完成交換後排列變為 [4,5,3,6,2,1][4,5,3,6,2,1]，此時我們可以重排「較小數」右邊的序列，序列變為 [4,5,3,1,2,6][4,5,3,1,2,6]。

算法過程

标準的“下一個排列”算法可以描述為：

從後向前查找第一個相鄰升序的元素對 (i,j)，滿足 A[i] < A[j]。此時 [j,end) 必然是降序

在 [j,end) 從後向前查找第一個滿足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所說的「小數」、「大數」

将 A[i] 與 A[k] 交換

可以斷定這時 [j,end) 必然是降序，逆置 [j,end)，使其升序

如果在步驟 1 找不到符合的相鄰元素對，說明目前 [begin,end) 為一個降序順序，則直接跳到步驟 4

 代碼實作

public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


    //基于雙指針将有序數組逆序,這是個可以學習的技巧
    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }