LeetCode-31.下一个排列

向右看齐 2022-01-31 15:55 155阅读 0赞

# 题目 #

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

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

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

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

解题思路—**反向遍历**：这题其实是典型的**找规律题**，怎么能快速找到规律，举几个极端的例子即可：

> 1.  **12345678**  
>     这个序列的下一个序列为 12345687， 即全部正序时，只需要交换最后两位数字即可。
> 2.  **87654321**  
>     这个序列的下一个序列为 12345678， 即全部逆序时，将字符串从头到尾翻转即可。
> 3.  **14562783**  
>     这个序列的下一个序列为 14562837，怎么翻转呢，从尾部开始遍历，因为要找到后面数字翻转的位置。（从头开始遍历容易遇到先增后减又增等情况，无法明确位置。）当序列中的数字全部处于逆序时，当前序列最大，即例子中的83，8左边的7是83序列的头，783组成序列最大的头应该是8，所以需要将7与83中比7大一点的数字交换，即7与8交换，变成873，但是以8开头最小的序列为837，所以还需要把后两位73翻转变成37。

所以总结一下找到下一个排列的过程：

> **当前有数字nums\[0…i…j\]，从尾部遍历，找到nums\[i-1\]<nums\[i\]，提取出nums\[i-1\]，将nums\[i-1\]与后面nums\[i…j\]相比，找出比nums\[i-1\]大一点的数，将其交换，再将nums\[i…j\]翻转即可。**

下面有两份解题代码，虽然思路是一样的，但是第一次写只写出了基础版，**精简版是LeetCode官方解答**，将所有情况完美的合在了一起，膜拜一下。

## Java解题—基础版 ##

class Solution {
        public void nextPermutation(int[] nums) {
            int i = nums.length - 2;
            while(i>=0 && nums[i+1]<=nums[i])
                i--;
            if(i==nums.length-2 && i>=0) // 全部逆序
                swap(nums, nums.length-2, nums.length-1);
            else if(i>=0){
                int j = i + 1;
                while(j<nums.length && nums[i]<nums[j])
                    j++;
                swap(nums, i, j-1);
                reverse(nums, i+1);
            }else // 全部正序
                reverse(nums, 0);
        }
        
        public static void reverse(int[] nums, int i){
            int j = nums.length - 1;
            while(i<j){
                swap(nums, i, j);
                i++;
                j--;
            }
        }
    
        public static void swap(int[] input, int i, int j){
            int temp = input[i];
            input[i] = input[j];
            input[j] = temp;
        }
    }

## Java解题—精简版 ##

class Solution {
        public void nextPermutation(int[] nums) {
            int i = nums.length - 2;
            while(i>=0 && nums[i+1]<=nums[i])
                i--;
            if(i>=0){ // 全部正序时，i=nums.length - 2； j=nums.length-1;
                int j = nums.length-1;
                while(j>i && nums[j]<=nums[i])
                    j--;
                swap(nums, i, j); //  全部正序时，即倒数两位翻转
            }
            reverse(nums, i+1); // 全部逆序时，i=-1； 全部正序时，i=nums.length - 2；
        }
        
        public static void reverse(int[] nums, int i){
            int j = nums.length - 1;
            while(i<j){
                swap(nums, i, j);
                i++;
                j--;
            }
        }
    
        public static void swap(int[] input, int i, int j){
            int temp = input[i];
            input[i] = input[j];
            input[j] = temp;
        }
    }