【LeetCode】31. 下一个排列【中等】

ゞ浴缸里的玫瑰 2022-11-10 10:47 155阅读 0赞

## 题目链接 ##

[31. 下一个排列【中等】][31.]

## 题目简介 ##

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

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

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

**示例 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.  我们可以将该问题形式化地描述为：给定若干个数字，将其组合为一个整数。如何将这些数字重新排列，以得到下一个更大的整数。如 **123** 下一个更大的数为 **132**。如果没有更大的整数，则输出最小的整数。
2.  我们希望下一个数字比 **当前的数字大**，这样才能满足 **下一个排列** 的定义。因此只需要 **将后面的【大数】与前面的【小数】交换**，就能得到一个更大的数。比如：`123456`，将 `5` 和 `6` 进行交换即可，就能得到一个更大的数字 `123465`
3.  我们希望下一个数字增幅尽量的小，这样才满足 **下一个排列与当前排列紧邻** 的要求，为了满足这个要求，我们需要
    
     *  在 **尽可能靠右的低位** 进行交换，需要 **从后往前** 扫描
     *  将一个 **尽可能小的【大数】** 与 **前面的【小数】** 交换。比如 `123465`，下一个排列应该把 `5` 和 `4` 交换而不是把 `6` 和 `4` 交换
     *  将【大数】换到前面后，需要将大数后面的所有数 **重新进行排序，保证升序序列就是最小的排列**。
     *  以 `123465` 为例，我们在将 `5` 和 `4` 交换后，得到 `123564`，然后需要将 `5` 之后的数重新进行排序，也就是 `123546`

## 题目代码 ##

public void nextPermutation(int[] nums) {
        
            if(nums.length == 0 || nums.length == 1){
        
                return;
            }
            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[j] <= nums[i]){
        
                    j--;
                }
                swap(nums, i, j);
            }
            resver(nums, i + 1, nums.length - 1);
        }
    
        public void swap(int[] nums, int i, int j){
        
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    
    
        public void resver(int[] nums, int start, int end){
        
            while(start <= end){
        
                swap(nums, start, end);
                start++;
                end--;
            }
        }

[31.]: https://leetcode-cn.com/problems/next-permutation/