Keshawn_lu's Blog

Leetcode 31. 下一个排列

数组
字数统计: 576阅读时长: 2 min
2020/11/10 Share

题目简介：

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

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

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

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1
2
3
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

思路：

这题看了题解以后感觉还是有点懵懵的，像是脑筋急转弯题一样，下面是个人的一点理解。

首先是从后往前遍历，找到第一个破坏升序的元素位置pos（即nums[pos ... ]为降序数组），由于降序是最大的序列，所以我们先将后面降序的数组翻转，这样就变成了最小的升序数组了。

来个例子会更加清楚一点，如[5,7,6,4,3] -> [6,3,4,5,7]，由于原数组是5开头的最大数组了，所以下一个排列必是6开头的，并且6后面的数组必是最小的升序。

所以我们先将nums[pos ...]翻转，变成[5,3,4,6,7]，然后在升序数组[3,4,6,7]中找到第一个比5的数字6（同样也是最接近5的数），将其与5交换，从而变成了[6,3,4,5,7]，可以注意到，交换以后，原来是升序的数组现在还是升序的，说明这就是最小的组合了。

tip:

  • pos == 0时，说明原本数组是最大的排列，下一个排列只需将其翻转，就是最小的升序了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    void nextPermutation(vector<int>& nums) {

        int pos = nums.size() - 1;

        while(pos > 0 && nums[pos] <= nums[pos - 1])	//注意是<=
            pos--;
        
        reverse(nums.begin() + pos, nums.end());    //翻转后面的降序为升序

        //原本数组一直是降序(最大),下一个排列便为翻转后的升序(最小)
        if(pos == 0)
            return;

        for(int i = pos; i < nums.size(); i++){

            if(nums[i] > nums[pos - 1]){

                //找到第一个比nums[pos - 1]大的数(也是最接近的)
                swap(nums[i], nums[pos - 1]);   
                break;
            }
        }
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网