31. 下一个排列

题目链接：https://leetcode-cn.com/problems/next-permutation/

难度：中等

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

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

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解法一：

“下一个排列”的定义是：给定数字序列的字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

我们可以将该问题形式化地描述为：给定若干个数字，将其组合为一个整数。如何将这些数字重新排列，以得到下一个更大的整数。如 123 下一个更大的数为 132。如果没有更大的整数，则输出最小的整数。

算法思路：

（1）如果要找到一个比目前数字大的数，一定是把一个比较靠后位置的大数和前面的一个小数进行了交换。

（2）如果要找到一个下一个排列，那么这个小数的位置i尽可能的靠后，那么我们就需要从后往前找，找到这个尽可能小的小数下标为i后；

（3）再找个尽可能小的大数，最终为了满足条件，这个大数也要尽可能靠后，所以我们也从后往前找，找到那个刚好比小数大的大数，大数的下标为j。

（4）交换后，这个数字就会比之前的数字大，但是还不是最佳的，我们上述得到的数字，从下标i以后的数字（不包括i），一定是降序排列的，因为上述的推理，类似于冒泡排序，所以，我们只要把 [i+1,len-1]，即下标i以后的数组进行倒置，变成升序，就是最后的结果了。

算法设计：

（1）从后往前找，找到第一个升序的元素 [i,i+1]，满足nums[i]<nums[i+1]，此时[i+1,len-1]一定是降序的。

（2）从后往前找，找到第一个大于元素nums[i]的下标k，即满足nums[i]<nums[k]，nums[i]就是所说的小数， nums[j]就是所说的大数。

（3）将 nums[i] 和nums[j]进行交换

（4）再将下标为[i+1,len-1]进行倒置，即将i+1往后的元素进行倒置。

（5）如果没有找到那个小数，那么说明目前的数字是最大的，那么我们就需要返回最小数，即将整个数组倒置，即进行第(4)步。

代码：

class Solution {
        public void nextPermutation(int[] nums) {
        if (nums.length == 0 || nums.length == 1) {
            return;
        }

        int i = 0;
        for (i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                break;
            }
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j > i) {
                if (nums[i] < nums[j]) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    break;
                }
                j--;
            }
        }

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