Leetcode31. 下一个排列

2021年5月10日 206点热度 0人点赞 0条评论

题目描述

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

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

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

示例 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]

提示:

  • 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());
}

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论