31. 下一个排列 - 力扣（LeetCode）

发表于 更新于 分类于 阅读次数： Disqus：

题目描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 必须原地修改，只允许使用额外常数空间。 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

题解

这里借用官方题解的一张动图来加深理解解法。 如果整个序列是降序的，则它是排列中最大字典序，没有其它排列的字典序比它还要大。那么我们第一步就是从右往左循环一遍，看是否存在nums[i - 1] < nums[i]；不存在，则直接按题意将整个序列逆序；存在，则再从右往左扫一遍，找第一个比nums[i - 1]大的数nums[j]，交换nums[i - 1]与nums[j]的位置。再把nums[i - 1]后的序列(降序)逆序为升序。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int len = nums.size(), i = len - 1;
        int j = len - 1, tmp;
        while(i > 0 &&nums[i] <= nums[i - 1]) --i;//寻找满足升序的相邻两个数
        if(i > 0){
            while(j >= 0 && nums[j] <= nums[i - 1]) --j;//找第一个比nums[i - 1]大的数，然后交换位置
            tmp = nums[i - 1];
            nums[i - 1] = nums[j];
            nums[j] = tmp;
        }
        reverse(nums.begin() + i, nums.end());//将nums[i - 1]后的序列逆序
    }
};

运行结果