（LeetCode）Java 求解下一个排列

刺骨的言语ヽ痛彻心扉 2022-10-24 01:42 122阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、代码
     *  三、总结

## 一、题目 ##

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

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

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

![在这里插入图片描述][20210128205423827.png]

--------------------

解析：  
这里的下一个更大的排序，指的是将数组中的数字重排后的按照字典序第一个比原来的序列大的序列。

> 比如：`nums=[1,2,3]`，那么对应的排序组合有\[1,3,2\]，\[2,1,3\]，\[2,3,1\]，\[3,1,2\]，\[3,2,1\]  
> 这其中如果按照在字典序，下一个比它大的就是 \[1,3,2\]

（1）我们希望下一个数比当前数大，这样才满足`下一个排列` 的定义。需要将后面的 “大数” 与前面的 “小数” 交换，这样就可以得到一个更大的数。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。  
（2）我们还希望下一个数增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求

*  从后往前找到一个较小的数，比如 124653，这里较小的数就是 4 ，下一步在 4 后找到一个比其大的数字和其发生交换
 *  对4后的数字重新排序，即得到 124356，然后在 4 后排好序的序列找第一个大于4的，也就是5,
 *  交换4,5得到12536

## 二、代码 ##

import java.util.Arrays;
    
    class Solution { 
        public void nextPermutation(int[] nums) { 
            if(nums==null||nums.length==1){ 
                return;
            }
            for(int i=nums.length-2;i>=0;i--){ 
                //从后往前找到一个较小的数
                if(nums[i]<nums[i+1]){ 
                    //将较小数后面的数字递增排序
                    Arrays.sort(nums,i+1,nums.length);
                    //在较小数后找到一个较大的数和其交换
                    for(int j=i+1;j<nums.length;j++){ 
                        if(nums[j]>nums[i]){ 
                            int temp = nums[i];
                            nums[i] = nums[j];
                            nums[j] = temp;
                            return;
                        }
                    }
    
                }
            }
            //如果上述条件不满足，则原序列是递减的序列，对其增序排列
            Arrays.sort(nums);
            return;
        }
    }
    public class Test_10 { 
    }

## 三、总结 ##

这个题重在思想，有两个关键的点，意识下一个排列要比原先的大，而是增大的幅度要尽可能的小

[20210128205423827.png]: /images/20221024/9967e9f9b51941939ec35fc1009f16af.png