[解题报告]《Leetcode》31-- 下一个排列

文章目录

1. 题目信息

1.1 题目描述

题目链接: 31. 下一个排列

实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须 原地 修改,只允许使用额外常数空间。

1.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 = [5]
输出:[1]
  • 示例 5:
输入:nums = [1,2,3,5,4,2,1]
输出:[1,2,4,1,2,3,5]
  • 提示:
1 <= nums.length <= 100
0 <= nums[i] <= 100

2. 题目分析

2.1 手动实现next_permutation

分三步完成, 从右往左找出一个最小的可以交换的数字对进行交换, 使得序列变大一点点, 我们以[1,2,3,5,4,2,1]为例;

  • 先逆序找到第一个可用于和后面的值交换的较小值, 即找到第一个不满足升序的值, 数组中的 3 就是我们要找的这个 第一个较小值, 假设 下标 i, 此处例子中值为 2;
  • 再逆序找到这个倒着看升序. 顺着看是降序的序列 [5,4,2,1] 中的值大于nums[i]的第一个下标 j, 使 nums[i] < nums[j], 然后交换这两个数字, 此处例子就是找到 比3略大的4, 然后交换, 得到新数组: [1, 2, 4, 5, 3, 2, 1];
  • 对 排在 (i, end) 也就是 [i+1, end)中的数字进行降序排列, 即直接逆序一下即可;

2.2 标准库的参考实现

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    if (first == last) return false;
    BidirIt i = last;
    if (first == --i) return false;
 
    while (true) {
        BidirIt i1, i2;
 
        i1 = i;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

3. 代码详情

3.1 C++

3.1.1 手动实现next_permutation

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if (next_permutation(nums.begin(), nums.end())) {
            return;
        }
        // 如果返回false, 说明已经达到最大的排列, 并且已经进行了逆转成最小序列;
        // cout << nums[0] << endl;
    }

    void nextPermutation_v1(vector<int>& nums) {
        // 执行用时:4 ms, 在所有 C++ 提交中击败了80.53%的用户
        // 内存消耗:11.8 MB, 在所有 C++ 提交中击败了49.02%的用户
        int i = nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i+1]) {
            i--;
        }

        // 找到从后往前的第一个下降值, 再次从后往前找到可以和这个值交换的第一个大于该下降值的值;
        if (i >= 0) {
            int j = nums.size() - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            // 一定可以找到这个合法的j;
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};

3.2 Python

4. 系列文章

上一篇:31. Next Permutation


下一篇:PS合成绚丽光影特效的美女真人插画图