下一个排列

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

  • 示例 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]

Solution

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <vector>
#include <bits/stdc++.h>

class Solution {
public:
    void nextPermutation(std::vector<int>& nums) {
        bool swap = false;
        int len = nums.size();
        for (int i = len - 1; i > 0; --i) {
            if (nums[i] > nums[i - 1]) {
                swap = true;
                int minIndex = i;
                for (int j = len - 1; j > i; --j) {
                    if (nums[j] > nums[i - 1]) {
                        minIndex = j;
                        break;
                    }
                }
                int tmp = nums[minIndex];
                nums[minIndex] = nums[i - 1];
                nums[i - 1] = tmp;
                
                std::reverse(nums.begin() + i, nums.end());
                break;
            }
        }
        // 取最小队列
        if (!swap) {
            std::reverse(nums.begin(), nums.end());
        };
    }
};

template <typename T>
void printVector(const std::vector<T> &data) {
    int len = data.size();
    std::cout << "{";
    for (int i = 0; i < len; ++i) {
        std::cout << data[i] << ", ";
    }
    std::cout << "}" << std::endl;
}

int main() {
    std::vector<int> input;
    
    input = {1,2,3}; // 1 3 2
    Solution().nextPermutation(input);
    printVector(input);

    input = {3, 2, 1}; // 1, 2, 3
    Solution().nextPermutation(input);
    printVector(input);

    input = {1,1,5}; // 1 5 1
    Solution().nextPermutation(input);
    printVector(input);

    input = {1}; // 1
    Solution().nextPermutation(input);
    printVector(input);

    input = {1, 3, 2}; // {2, 1, 3}
    Solution().nextPermutation(input);
    printVector(input);

    input = {2,3,1}; // {3, 1, 2}
    Solution().nextPermutation(input);
    printVector(input);

    input = {2,2,7,5,4,3,2,2,1}; // [2,3,1,2,2,2,4,5,7]
    Solution().nextPermutation(input);
    printVector(input);
    return 0;
}