leetcode31：下一个排列

题目链接

leetcode

题目描述

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如：arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，[1,2,3] 的下一个排列是 [1,3,2] 。
• [2,3,1] 的下一个排列是 [3,1,2] 。
• [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

已知：一个整数数组 nums ，找出 nums 的下一个排列。
要求：必须原地修改，只允许使用额外常数空间。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
    找规律

    从后向前找第一个降序的位置（下降点），
    从后向前找第一个大于它的数（交换点）
    该位置之后的部分反转，调整为升序。

    时间复杂度：O(n)
        查找下降点，O(n)
        查找交换点，O(n)
        反转，O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n-2;

        // 从后向前找第一个  nums[i] < nums[i+1]
        while (i >= 0 && nums[i] >= nums[i+1]) {
            i--;
        }

        if (i >= 0) {
            // 从后向前找第一个大于 nums[i] 的数
            int j = n-1;
            while (j > i && nums[j] <= nums[i]) {
                j--;
            }
            // 交换 nums[i] 和 nums[j]
            swap(nums[i], nums[j]);
        }

        // 反转 i+1 到末尾部分，这部分变为最小排列
        reverse(nums.begin()+i+1, nums.end());
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {1,2,3},
        {3,2,1},
        {1,1,5},
    };

    for (auto& nums : nums_cases) {
        cout << "Input: nums = ";
        printArray(nums);
        cout << endl;

        solution.nextPermutation(nums);
        cout << "Output: ";
        printArray(nums);
        cout << endl;
    }

    return 0;
}