下一个排列

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation

题目描述：

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。

示例 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]

思路:

1. 从后往前找到数字nums中的第一个升序,nums[i] < nums[i + 1],a = i, b = i + 1
2. 再次从后往前找到第一个大于nums[i]的数字nums[k],交换nums[i],nums[k]的位置
3. 对索引b及之后的数进行升序排序.

4. 如果在步骤1中找不到nums[i] < nums[i + 1]则说明不存在下一个更大排列,直接对数组进行升序排列.

   
   31. 下一个排列

代码实现:

class Solution {
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        boolean flag = false;
        int a = 0, b = 0;
        for (int i = len - 1; i >= 1; i--) {
            int j = i - 1;
            // 从后往前遍历,寻找第一个升序数字
            if (nums[j] < nums[i]) {
                flag = true;
                a = j;
                b = i;
                break;
            }
        }
        if (flag) {
            // 从后往前遍历,寻找第一个大于nums[a]的数字,交换位置.
            for (int i = len - 1; i >= 0; i--) {
                if (i > a && nums[i] > nums[a]) {
                    int temp = nums[i];
                    nums[i] = nums[a];
                    nums[a] = temp;
                    break;
                }
            }
            // 对索引b及之后的数字进行升序排列
            for (int i = b; i < len - 1; i++) {
                for (int j = i + 1; j < len; j++) {
                    if (nums[i] > nums[j]) {
                        int temp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = temp;
                    }
                }
            }
            // nums[0] = b;
        } else {
            // 不存在下一个更大的数字排列
            Arrays.sort(nums);
        }
    }
}