题目描述

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

给出一个序列，找出这个序列在字典序中的下一个排列，如果这个序列没有下一个字典序排列（说明是字典序最后一个，即逆序），则给出最小的字典序（再从字典序的第一个开始，也就是顺序）。
置换必须是原地排序，例子如上。

前置知识

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

在数学中，字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法。 这种泛化主要在于定义有序完全有序集合（通常称为字母表）的元素的序列（通常称为计算机科学中的单词）的总顺序。

也就是说，字典序就像是在查一个字典，例如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时，可以保证高位的增大。在交换时为了找到字典序的下一个，所以要从右侧的542中选择刚好比3大的数（4）和3进行交换，得到序列1,4,5,3,2。
至此高位已经确定，但是低位的排列是一个逆序排列

交换完532形成逆序

逆序是字典序中最大的排列，因此在交换元素之后，还要将后面的逆序翻转成顺序。

逆序翻转为顺序

代码实现

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后面的数必定是逆序，逆序是字典序最大的，因此翻转，换成顺序，顺序是字典序里最小的
                        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;
        }
}

在寻找尽量小的下一个元素时，因为右边已经形成逆序，可以采用二分查找缩短查找时间。

    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);
        }
    }