Leetcode31. 下一个排列

题目描述

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

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

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

示例 1：

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

示例 2：

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

示例 3：

1 2	输入：nums = [1,1,5] 输出：[1,5,1]

示例 4：

1 2	输入：nums = [1] 输出：[1]

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100

解题思路

这道题的题目有亿点难懂！！！

先看看啥叫下一个排列。以数字序列 $[1,2,3]$ 为例，其排列按照字典序以此为：

$[1,2,3] \\\\ [1,3,2] \\\\ [2,1,3] \\\\ [2,3,1] \\\\ [3,1,2] \\\\ [3,2,1] \\\\$

这样，排列 $[2,3,1]$ 的下一个排列即为 $[3,1,2]$ 。特别的，最大的排列 [$3,2,1] $的下一个排列为最小的排列 $[1,2,3]$ 。

观察排列的规律，下一个排列组成的数字总是比当前排列组成的数字要大，除非是最后一个排列。那么根据题目的要求，我们需要找到一个比当前序列大，但是变化幅度最小的排列。

根据排列的规律，我们可以设计出以下算法：

从后往前遍历，找出第一个当前数比后面一个数小的数字，它的下标记为 $index$ ;
然后重新开始从后往前遍历，找到 $index$ 坐标后的数字中第一个比 $index$ 所指数字大的数字，它的下标记为 $k$ ；
交换 $index$ 和 $k$ 所指的数字；
将 $index$ 后面的所有数字反转。

根据所述算法，我们可以写出对应的代码。

示例代码

void nextPermutation(vector<int>& nums)
{
    if(nums.empty()||nums.size()==1) return;
    int index=nums.size()-2;
    for(;index>=0;--index)
    {
        if(nums[index]<nums[index+1]) break;
    }
    cout<<index<<endl;
    if(index>=0)
    {
        int k=nums.size()-1;
        for(;k>=0;--k)
        {
            if(nums[index]<nums[k]) break;
        }
        cout<<k<<endl;
        swap(nums[index],nums[k]);
        reverse(nums.begin()+index+1,nums.end());
        return;

    }
    reverse(nums.begin(),nums.end());
}