題目描述

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

給出一個序列，找出這個序列在字典序中的下一個排列，如果這個序列沒有下一個字典序排列（說明是字典序最后一個，即逆序），則給出最小的字典序（再從字典序的第一個開始，也就是順序）。
置換必須是原地排序，例子如上。

前置知識

理解本題之前需要先理解字典序。

在數(shù)學中，字典或詞典順序（也稱為詞匯順序，字典順序，字母順序或詞典順序）是基于字母順序排列的單詞按字母順序排列的方法。 這種泛化主要在于定義有序完全有序集合（通常稱為字母表）的元素的序列（通常稱為計算機科學中的單詞）的總順序。

也就是說，字典序就像是在查一個字典，例如12345，先按照第一位的1來查，再查第二位...
上面例子中的1,2,3序列，按照字典序的下一位應該是1,2,4，但是需要123的排列，因此是1,3,2。

算法思路

這個題主要在于理解字典序，理解了字典序其余的就是遍歷和交換了。
例如序列1,3,5,4,2，因為要找到字典序的下一個，所以高位要盡可能不變動，所以從右邊看起。如果交換了2和4，最末位會增大，但是高位的4會變小，總體會變小。

保證了低位的增加，高位會變小，總體變小

所以應該盡量保證高位的增大，從右向左遍歷，4>2，5>4>2，都無法保證高位的增大，只有到3時，可以保證高位的增大。在交換時為了找到字典序的下一個，所以要從右側(cè)的542中選擇剛好比3大的數(shù)（4）和3進行交換，得到序列1,4,5,3,2。
至此高位已經(jīng)確定，但是低位的排列是一個逆序排列

交換完532形成逆序

逆序是字典序中最大的排列，因此在交換元素之后，還要將后面的逆序翻轉(zhuǎn)成順序。

逆序翻轉(zhuǎn)為順序

代碼實現(xiàn)

public void nextPermutation(int[] nums) {
        if (nums.length < 2) {
            return;
        }

        for (int i = nums.length - 2; i >= 0; i--) {
            // 找到nums[i1] < nums[i2]的
            if (nums[i] < nums[i + 1]) {
                int i1 = i;
                int i2 = i + 1;
                // 從后面找到第一個比nums[i1]大的（剛好比nums[i1]大的）
                for (int j = nums.length - 1; j >= i2; j--) {
                    if (nums[j] > nums[i1]) {
                        // 交換，以達到i1的位置被換到盡量小的下一個
                        int temp = nums[j];
                        nums[j] = nums[i1];
                        nums[i1] = temp;

                        // i1后面的數(shù)必定是逆序，逆序是字典序最大的，因此翻轉(zhuǎn)，換成順序，順序是字典序里最小的
                        for (int k = 0; k < (nums.length - i2) / 2; k++) {
                            int mid = nums[i2 + k];
                            nums[i2 + k] = nums[nums.length - 1 - k];
                            nums[nums.length - 1 - k] = mid;
                        }
                        return;
                    }
                }
            }
        }

        for (int i = 0; i < nums.length / 2; i++) {
            int mid = nums[i];
            nums[i] = nums[nums.length - 1 - i];
            nums[nums.length - 1 - i] = mid;
        }
}

在尋找盡量小的下一個元素時，因為右邊已經(jīng)形成逆序，可以采用二分查找縮短查找時間。

    public void nextPermutation(int[] nums) {

        if (nums.length < 2) {
            return;
        }

        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                int i1 = i;
                int i2 = i + 1;
                // 利用二分查找尋找比nums[i1]大的下一個
                int[] res = new int[1];
                findLastGreater(nums[i1], nums, i2, nums.length - 1, res);
                int j = res[0];
                // 進行交換
                int temp = nums[j];
                nums[j] = nums[i1];
                nums[i1] = temp;

                for (int k = 0; k < (nums.length - i2) / 2; k++) {
                    int mid = nums[i2 + k];
                    nums[i2 + k] = nums[nums.length - 1 - k];
                    nums[nums.length - 1 - k] = mid;
                }

                return;
            }
        }

        for (int i = 0; i < nums.length / 2; i++) {
            int mid = nums[i];
            nums[i] = nums[nums.length - 1 - i];
            nums[nums.length - 1 - i] = mid;
        }
    }

    private static void findLastGreater(int target, int[] nums, int start, int end, int[] res) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) / 2;
        if (nums[mid] > target) {
            res[0] = mid;
            findLastGreater(target, nums, mid + 1, end, res);
        } else {
            findLastGreater(target, nums, start, mid, res);
        }
    }