☆打卡算法☆LeetCode 31、下一个排列 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“将数组序列重新排列成下一个更大的排列，如果不存在下一个更大的排列，则将数组排列成最小的排列。”

题目链接：

来源：力扣（LeetCode）

链接：31. 下一个排列 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

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

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

示例 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、思路分析

这个题注意到下一个排列总是比当前排列要打，除非该排列已经是最大的排列。

那么，我们可以从后向前查找第一个较小数，此时是下降序列。

找到了顺序对，那么就从后前查找第一个满足的元素，这个元素就是较大数。

交换较小数和较大数，就可以证明这个区间为降序，使用双指针反转区间使其变成升序，则无需对该区间进行排序。

2、代码实现

代码参考：

public class Solution {
    /// <summary>
    /// 翻转数组双指针逆序
    /// </summary>
    /// <param name="nums"></param>
    public void NextPermutation(int[] nums)
    {
        int n = nums.Length;
        //排除特殊情况
        if (n <= 1) return;
        //双指针
        int left = n - 2;
        int right = n - 1;
        //翻转最小字串
        while (right - left < n)
        {
            for (int i = right; i >left; i--)
            {
                //查询字符串是否可以翻转
                if (nums[i]> nums[left])
                {
                    //翻转left,i指针
                    int temp = nums[i];
                    nums[i] = nums[left];
                    nums[left] = temp;
                    //翻转left指针后所有项
                    for (int j = left+1; j <= left+(right-left+1)/2; j++)
                    {
                        temp = nums[j];
                        nums[j] = nums[right-j+left+1];
                        nums[right - j + left+1] = temp;
                    }
                    return;
                }
            }
            left--;
        }
        //数组顺序翻转数组
        for (int i = 0; i < n/2; i++)
        {
            int temp = nums[i];
            nums[i] = nums[n - 1 - i];
            nums[n - 1 - i] = temp;
        }
        return;
    }
}

3、时间复杂度

时间复杂度 ： O(N)

其中N为给定序列的长度，我么只需要扫描两次序列，进行一次反转操作。

空间复杂度： O(1)

只需要常数级的空间存放若干变量。

三、总结

这题感觉考的就是数学思维，当思路想明白了，代码也就出来了。