31. 下一个排列题目描述解题过程总结

54 阅读 0 评论 36 点赞

我是靠谱客的博主紧张帽子，最近开发中收集的这篇文章主要介绍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]

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

解题过程

解题思路

这道题目首先要明白字典序的概念。
以下是参考自一篇博文的字典序描述：
从上面的全排列也可以看出来了，从左往右依次增大，对这就是字典序法。可是如何用算法来实现字典序法全排列呢？
我们再来看一段文字描述：（用字典序法找124653的下一个排列）
如果当前排列是124653，找它的下一个排列的方法是，从这个序列中从右至左找第一个左邻小于右邻的数
如果找不到，则所有排列求解完成，如果找得到则说明排列未完成
本例中将找到46，计4所在的位置为i,找到后不能直接将46位置互换，而又要从右到左到第一个比4大的数
本例找到的数是5，其位置计为j，将i与j所在元素交换125643
然后将i+1至最后一个元素从小到大排序得到125346，这就是124653的下一个排列
————————————————
版权声明：本文为CSDN博主「兰亭落雪」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37050329/article/details/86637183
根据上面的描述，想到以下解决思路：
1、找到数组从右往左的第一个左邻小于右邻的数的下标，即这个左邻的下标i；
2、再次从右往左找第一个比i位置数大的数的下标j；
3、根据i和j判断nums[j]是否大于nums[i]，若不是则表明不存在下一个更大的排列，将原数组从小到大排序即可，否则，交换nums[i]和nums[j]，同时将i+1之后的数按从小到大排序。

class Solution {
    public void nextPermutation(int[] nums) {

        int i = nums.length - 2;

        while(i >= 0 && nums[i] >= nums[i + 1]){
            i--;
        }
        int j = nums.length - 1;
        while(j >= 0 && i >= 0 && nums[j] <= nums[i]){
            j--;
        }
        if(i < 0 || j < 0 || nums[j] <= nums[i]){//不存在下一个更大的排列
            Arrays.sort(nums);
        }else{
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            //选择排序
            for(int k = i + 1; k < nums.length; k++){
                for(int z = k + 1; z < nums.length;z++){
                    if(nums[z] < nums[k]){
                        int tmp = nums[k];
                        nums[k] = nums[z];
                        nums[z] = tmp;
                    }
                }
            }
        }

    }
}