LeetCode刷题Java版031.下一个排列

作者：沉默王二
发布时间：2022-08-25T07:29:20.941+0800

---

031.下一个排列

题意

给你一个数组，让你求其字典序意义上的更大一个的排列，如果已经是最大的字典序，则返回最小的字典序。

题意似乎有些难理解，因为第一次看到“字典序”这个概念的时候，不能很好的理解它表达的意思。不过没关系，看一下示例和分析你就明白了。

难度

中等

示例

例1

输入：nums = [1,2,3]

例2

输入：nums = [3,2,1]

分析

字典序（dictionary order），又称 字母序（alphabetical order），原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两个任意字符串的大小关系。而这道题目中，字典序其实是指☞ 数字大小的先后顺序。

理解了“字典序”，就能很快理解这道题的题意了：要我们求出比这个数更大的一个排列，比如 123，比它大的是 132，对吧？只需要改变 23 的位置就可以了。312 也比 123 大，只不过它是比 132 更大的一个，不是比 123 更大的一个。

再比如 321 已经是这个组合中最大的那个了，那就等于说没有更大的了，所以返回 123 这个最小的。

明白了吧？

要想解题，首先得明白题意，所以语文理解是非常重要的，其次是经验。

那凭我们的经验，可能一下子会想到全排列，然后再挨个找，最后输出这个排列的下一个排列，可惜这样子时间复杂度太高了——也就是，实在是顶不住啊！

但是没关系，我们先来观察一下数组（就拿 1、2、3、4 来举例吧）的全排列：

nums = [1,2,3,4]

nums = [1,3,2,4]nums = [1,3,4,2]nums = [1,4,2,3]nums = [1,4,3,2]nums = [2,1,3,4]nums = [2,1,4,3]nums = [2,3,1,4]nums = [2,3,4,1]nums = [2,4,1,3]nums = [2,4,3,1]nums = [3,1,2,4]nums = [3,1,4,2]nums = [3,2,1,4]nums = [3,2,4,1]nums = [3,4,1,2]nums = [3,4,2,1]nums = [4,1,2,3]nums = [4,1,3,2]nums = [4,2,1,3]nums = [4,2,3,1]nums = [4,3,1,2]nums = [4,3,2,1]

这道题中，我们可以把字典序理解成一个进制为INF的一个数字，这样子就可以比较直观的比较大小了。而下一个排列，就是要你用现在已有的数字组合出一个 恰好 比它大的一个新的进制为INF的数字。而且要让这个新的数尽可能小。

观察nums = [1,3,4,2] -> nums = [1,4,2,3]这一步，因为4比3大，且4的位置在3之后，所以将4与3交换，必然能够使得nums变大，交换了之后，则变成了nums = [1,4,3,2]。

我们看一下上面列出来的范例，显然这不是最小的比nums = [1,3,4,2]大的一个排列，我们还要把3和2的位置再翻转一下，才能得到nums = [1,4,2,3]这个 恰好 比nums = [1,3,4,2]大的排列。

但是我们不能直接交换1和3，因为这样子迈的步子有点大，有没有快速找到两个需要交换的数字的一个标准呢？

观察上面的全排列，我们不难得出，需要寻找的是一个从右到左的第一个nums[i] < nums[i + 1]的数字，而这时候，我们能够保证[i + 1,nums.length )必然是下降的。

有些小伙伴，可能会想着——直接交换nums[i]和nums[i + 1]，这样子可行吗？

事实上不行，因为我们为了让新的数列最小，不能直接交换二者，因为如果[i + 1,nums.length )中存在有一个nums[k]比nums[i]大，且同时比nums[i + 1]小的数字，显然直接交换nums[i]和nums[k]更合理一点，因为它交换之后是比交换nums[i]和nums[i + 1]更小。

所以到这里，这道题目就迎刃而解了。

具体代码实现：

class Solution {

        int temp = nums[posI];        nums[posI] = nums[posJ];        nums[posJ] = temp;    }    private void reverse(int[] nums, int lef, int rig){        while(lef < rig){            swap(nums,lef,rig);            lef++;            rig--;        }    }    public void nextPermutation(int[] nums) {        int pos1 = nums.length - 2;        while(pos1 >= 0 && nums[pos1] >= nums[pos1 + 1])            pos1--;        if(pos1 == -1){            reverse(nums,0,nums.length - 1);            return ;        }        int pos2 = nums.length - 1;        for(int i = nums.length - 1;i >= 0;i--){            if(nums[i] > nums[pos1]){                pos2 = i;                break;            }        }        swap(nums,pos1,pos2);        reverse(nums,pos1 + 1,nums.length - 1);    }}

效率嘛，自然是快得飞起，因为我们只是扫描了一下数组，只需要的时间复杂度即可。

总结

本题如果直接 莽 ，去求所有的排列的话，我想可能没有哪个CPU能够在我们预期的时间内给出答案。我们之所以学习算法，就是想让我们拥有更快的能够解决问题的方法。硬件的进步是时代的进步，而我们个人的智慧，才能够使我们脱颖而出。

力扣链接：https://leetcode.cn/problems/next-permutation/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 700 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

031.下一个排列

题意

给你一个数组，让你求其字典序意义上的更大一个的排列，如果已经是最大的字典序，则返回最小的字典序。

题意似乎有些难理解，因为第一次看到“字典序”这个概念的时候，不能很好的理解它表达的意思。不过没关系，看一下示例和分析你就明白了。

难度

中等

示例

例1

输入：nums = [1,2,3]

例2

输入：nums = [3,2,1]

分析

字典序（dictionary order），又称 字母序（alphabetical order），原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两个任意字符串的大小关系。而这道题目中，字典序其实是指☞ 数字大小的先后顺序。

理解了“字典序”，就能很快理解这道题的题意了：要我们求出比这个数更大的一个排列，比如 123，比它大的是 132，对吧？只需要改变 23 的位置就可以了。312 也比 123 大，只不过它是比 132 更大的一个，不是比 123 更大的一个。

再比如 321 已经是这个组合中最大的那个了，那就等于说没有更大的了，所以返回 123 这个最小的。

明白了吧？

要想解题，首先得明白题意，所以语文理解是非常重要的，其次是经验。

那凭我们的经验，可能一下子会想到全排列，然后再挨个找，最后输出这个排列的下一个排列，可惜这样子时间复杂度太高了——也就是，实在是顶不住啊！

但是没关系，我们先来观察一下数组（就拿 1、2、3、4 来举例吧）的全排列：

nums = [1,2,3,4]

nums = [1,3,2,4]nums = [1,3,4,2]nums = [1,4,2,3]nums = [1,4,3,2]nums = [2,1,3,4]nums = [2,1,4,3]nums = [2,3,1,4]nums = [2,3,4,1]nums = [2,4,1,3]nums = [2,4,3,1]nums = [3,1,2,4]nums = [3,1,4,2]nums = [3,2,1,4]nums = [3,2,4,1]nums = [3,4,1,2]nums = [3,4,2,1]nums = [4,1,2,3]nums = [4,1,3,2]nums = [4,2,1,3]nums = [4,2,3,1]nums = [4,3,1,2]nums = [4,3,2,1]

这道题中，我们可以把字典序理解成一个进制为INF的一个数字，这样子就可以比较直观的比较大小了。而下一个排列，就是要你用现在已有的数字组合出一个 恰好 比它大的一个新的进制为INF的数字。而且要让这个新的数尽可能小。

观察nums = [1,3,4,2] -> nums = [1,4,2,3]这一步，因为4比3大，且4的位置在3之后，所以将4与3交换，必然能够使得nums变大，交换了之后，则变成了nums = [1,4,3,2]。

我们看一下上面列出来的范例，显然这不是最小的比nums = [1,3,4,2]大的一个排列，我们还要把3和2的位置再翻转一下，才能得到nums = [1,4,2,3]这个 恰好 比nums = [1,3,4,2]大的排列。

但是我们不能直接交换1和3，因为这样子迈的步子有点大，有没有快速找到两个需要交换的数字的一个标准呢？

观察上面的全排列，我们不难得出，需要寻找的是一个从右到左的第一个nums[i] < nums[i + 1]的数字，而这时候，我们能够保证[i + 1,nums.length )必然是下降的。

有些小伙伴，可能会想着——直接交换nums[i]和nums[i + 1]，这样子可行吗？

事实上不行，因为我们为了让新的数列最小，不能直接交换二者，因为如果[i + 1,nums.length )中存在有一个nums[k]比nums[i]大，且同时比nums[i + 1]小的数字，显然直接交换nums[i]和nums[k]更合理一点，因为它交换之后是比交换nums[i]和nums[i + 1]更小。

所以到这里，这道题目就迎刃而解了。

具体代码实现：

class Solution {

        int temp = nums[posI];        nums[posI] = nums[posJ];        nums[posJ] = temp;    }    private void reverse(int[] nums, int lef, int rig){        while(lef < rig){            swap(nums,lef,rig);            lef++;            rig--;        }    }    public void nextPermutation(int[] nums) {        int pos1 = nums.length - 2;        while(pos1 >= 0 && nums[pos1] >= nums[pos1 + 1])            pos1--;        if(pos1 == -1){            reverse(nums,0,nums.length - 1);            return ;        }        int pos2 = nums.length - 1;        for(int i = nums.length - 1;i >= 0;i--){            if(nums[i] > nums[pos1]){                pos2 = i;                break;            }        }        swap(nums,pos1,pos2);        reverse(nums,pos1 + 1,nums.length - 1);    }}

效率嘛，自然是快得飞起，因为我们只是扫描了一下数组，只需要的时间复杂度即可。

总结

本题如果直接 莽 ，去求所有的排列的话，我想可能没有哪个CPU能够在我们预期的时间内给出答案。我们之所以学习算法，就是想让我们拥有更快的能够解决问题的方法。硬件的进步是时代的进步，而我们个人的智慧，才能够使我们脱颖而出。

力扣链接：https://leetcode.cn/problems/next-permutation/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 700 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

031.下一个排列

题意

给你一个数组，让你求其字典序意义上的更大一个的排列，如果已经是最大的字典序，则返回最小的字典序。

题意似乎有些难理解，因为第一次看到“字典序”这个概念的时候，不能很好的理解它表达的意思。不过没关系，看一下示例和分析你就明白了。

难度

中等

示例

例1

输入：nums = [1,2,3]

例2

输入：nums = [3,2,1]

分析

字典序（dictionary order），又称 字母序（alphabetical order），原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两个任意字符串的大小关系。而这道题目中，字典序其实是指☞ 数字大小的先后顺序。

理解了“字典序”，就能很快理解这道题的题意了：要我们求出比这个数更大的一个排列，比如 123，比它大的是 132，对吧？只需要改变 23 的位置就可以了。312 也比 123 大，只不过它是比 132 更大的一个，不是比 123 更大的一个。

再比如 321 已经是这个组合中最大的那个了，那就等于说没有更大的了，所以返回 123 这个最小的。

明白了吧？

要想解题，首先得明白题意，所以语文理解是非常重要的，其次是经验。

那凭我们的经验，可能一下子会想到全排列，然后再挨个找，最后输出这个排列的下一个排列，可惜这样子时间复杂度太高了——也就是，实在是顶不住啊！

但是没关系，我们先来观察一下数组（就拿 1、2、3、4 来举例吧）的全排列：

nums = [1,2,3,4]

nums = [1,3,2,4]nums = [1,3,4,2]nums = [1,4,2,3]nums = [1,4,3,2]nums = [2,1,3,4]nums = [2,1,4,3]nums = [2,3,1,4]nums = [2,3,4,1]nums = [2,4,1,3]nums = [2,4,3,1]nums = [3,1,2,4]nums = [3,1,4,2]nums = [3,2,1,4]nums = [3,2,4,1]nums = [3,4,1,2]nums = [3,4,2,1]nums = [4,1,2,3]nums = [4,1,3,2]nums = [4,2,1,3]nums = [4,2,3,1]nums = [4,3,1,2]nums = [4,3,2,1]

这道题中，我们可以把字典序理解成一个进制为INF的一个数字，这样子就可以比较直观的比较大小了。而下一个排列，就是要你用现在已有的数字组合出一个 恰好 比它大的一个新的进制为INF的数字。而且要让这个新的数尽可能小。

观察nums = [1,3,4,2] -> nums = [1,4,2,3]这一步，因为4比3大，且4的位置在3之后，所以将4与3交换，必然能够使得nums变大，交换了之后，则变成了nums = [1,4,3,2]。

我们看一下上面列出来的范例，显然这不是最小的比nums = [1,3,4,2]大的一个排列，我们还要把3和2的位置再翻转一下，才能得到nums = [1,4,2,3]这个 恰好 比nums = [1,3,4,2]大的排列。

但是我们不能直接交换1和3，因为这样子迈的步子有点大，有没有快速找到两个需要交换的数字的一个标准呢？

观察上面的全排列，我们不难得出，需要寻找的是一个从右到左的第一个nums[i] < nums[i + 1]的数字，而这时候，我们能够保证[i + 1,nums.length )必然是下降的。

有些小伙伴，可能会想着——直接交换nums[i]和nums[i + 1]，这样子可行吗？

事实上不行，因为我们为了让新的数列最小，不能直接交换二者，因为如果[i + 1,nums.length )中存在有一个nums[k]比nums[i]大，且同时比nums[i + 1]小的数字，显然直接交换nums[i]和nums[k]更合理一点，因为它交换之后是比交换nums[i]和nums[i + 1]更小。

所以到这里，这道题目就迎刃而解了。

具体代码实现：

class Solution {

        int temp = nums[posI];        nums[posI] = nums[posJ];        nums[posJ] = temp;    }    private void reverse(int[] nums, int lef, int rig){        while(lef < rig){            swap(nums,lef,rig);            lef++;            rig--;        }    }    public void nextPermutation(int[] nums) {        int pos1 = nums.length - 2;        while(pos1 >= 0 && nums[pos1] >= nums[pos1 + 1])            pos1--;        if(pos1 == -1){            reverse(nums,0,nums.length - 1);            return ;        }        int pos2 = nums.length - 1;        for(int i = nums.length - 1;i >= 0;i--){            if(nums[i] > nums[pos1]){                pos2 = i;                break;            }        }        swap(nums,pos1,pos2);        reverse(nums,pos1 + 1,nums.length - 1);    }}

效率嘛，自然是快得飞起，因为我们只是扫描了一下数组，只需要的时间复杂度即可。

总结

本题如果直接 莽 ，去求所有的排列的话，我想可能没有哪个CPU能够在我们预期的时间内给出答案。我们之所以学习算法，就是想让我们拥有更快的能够解决问题的方法。硬件的进步是时代的进步，而我们个人的智慧，才能够使我们脱颖而出。

力扣链接：https://leetcode.cn/problems/next-permutation/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 700 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412