Next Permutation

31. Next Permutation

分析

通过观察可以发现：

字典序的下一个排列是在现有排列的基础上，从右往左找到某个位置调整以得到更大的排列，同时调整后尽可能小
当数组已经是降序排列时，不存在更大的排列，此时直接将其翻转为最小排列

步骤如下：

从右往左找到第一个递减的数：
- 从后往前找到第一个位置 k-1，满足 nums[k-1] < nums[k]。此时，nums[k-1]是需要调整的“转折点”
- 如果不存在这样的 k-1，说明整个数组是降序排列，直接反转数组即可
从左往右找到最后一个比 nums[k-1] 大的数：
- 从 k 开始向右遍历，找到最后一个比 nums[k-1] 大的数，记为 nums[t]
交换 nums[k-1] 和 nums[t]
反转 nums[k] 到数组末尾的元素：
- 确保调整后的部分是最小的排列，符合字典序规则

时间复杂度

寻找递减位置：O(n)
找到交换位置：O(n)
反转数组：O(n)

总时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 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 k = nums.size() - 1;  // 初始化指针从右向左寻找
        while (k > 0 && nums[k - 1] >= nums[k])  // 找到第一个递减的数
            --k;

        if (k <= 0)  // 如果整个数组是降序排列，直接反转
        {
            std::reverse(nums.begin(), nums.end());
        }
        else
        {
            int t = k;
            // 从左向右找到比 nums[k-1] 大的最后一个数
            while (t < nums.size() && nums[k - 1] < nums[t])
                ++ t;
            // 交换 nums[k-1] 和 nums[t-1]
            std::swap(nums[k - 1], nums[t - 1]);

            // 反转 nums[k] 到末尾的部分
            std::reverse(nums.begin() + k, nums.end());
        }
    }
};