Leetcode 31. 下一个排列

拼搏现实的明天。 2022-09-07 01:22 172阅读 0赞

#### 题目重述 ####

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

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

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

##### 示例 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.length <= 100  
0 <= nums\[i\] <= 100

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/next-permutation  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

记录一下，参考[https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-yi-kan-jiu-dong-by-ych-983q/][https_leetcode-cn.com_problems_next-permutation_solution_xia-yi-ge-pai-lie-yi-kan-jiu-dong-by-ych-983q]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]  
需要注意的是，找到第一个“前面的小于后面的”,此时current之后的都是有序的，找到第一个比current大的，此时交换后，则是下一个想要的较大的，例如测试样例\[1,3,2\]，结果应该是\[2,1,3\]

#### Java实现 ####

class Solution {
        
        public void nextPermutation(int[] nums) {
        
            int current = nums.length -2;
            // 从后往前找，用来判断是否是最大数了
            while (current>=0 && nums[current]>=nums[current+1]){
        
                current-- ;
            }
            if(current < 0){
        
                Arrays.sort(nums);
            }else{
        
                // 找到第一个,此时current之后的都是有序的，找到第一个比current大的，此时交换后，则是下一个想要的较大的，例如测试样例[1,3,2]，结果应该是[2,1,3]
                int firstBig = nums.length - 1;
                while(nums[firstBig] <= nums[current]){
        
                    firstBig--;
                }
                // 交换，此时current之后的都是有序的，这时候将后面的部分逆序，即得到下一个排列
                int t = nums[current];
                nums[current] = nums[firstBig];
                nums[firstBig] = t;
                // 逆序
                reverse(nums,current+1);
    
            }
        }
        // 1 2 3 4   0,3
        public void reverse(int[] nums, int start) {
        
            int left = start, right = nums.length - 1;
            while (left < right) {
        
                int t = nums[left];
                nums[left] = nums[right];
                nums[right] = t;
                left++;
                right--;
            }
        }
    }

[https_leetcode-cn.com_problems_next-permutation_solution_xia-yi-ge-pai-lie-yi-kan-jiu-dong-by-ych-983q]: https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-yi-kan-jiu-dong-by-ych-983q/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]: /images/20220829/1b4fa56a0a1e4b8d89c955b0d9cd494b.png