LeetCode31 下一个排列

发表于 | 分类于 |
字数统计: 427 | 阅读时长 ≈ 1

链接: https://leetcode-cn.com/problems/next-permutation/

题意

给你一个整数数组 nums ，找出 nums 的下一个排列。整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。

解法

将序列视为数字，以3个数的全排列为例
123, 132, 213, 231, 312, 321
每次下一个数字是要比上一个数大，但是增大的幅度要求是最小的

来源：https://www.jianshu.com/p/b31f54cf0c54
因此可以考虑如下的算法：

  1. 从右到左进行扫描,发现第一个违背递增趋势的数字,称之为 PartitionNumber, 如上图,6恰好是我们找到的 PartitionNumber .
  2. 从右到左进行扫描,发现第一个比 PartitionNumber 要大的数,称之为 ChangeNumber.而7恰好是我们找到的 ChangeNumber ,需要注意的是,这样的数一定是存在的,否则的话,就找不到所以的 PartitionNumber 了.
  3. 交换 PartitionNumber 和 ChangeNumber.这样一步,会使得新的排列组成的数比旧的排列组成的数要大,当然,新数增长的幅度不一定是最小的.
  4. 反转在 PartitionNumber 右侧的数.此时, PartitionNumber 右侧的排列已经是严格的从大到小排列了,如此反转之后,可以保证,新的排列组成的数的增长幅度在所有的可能中最小.

代码

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
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int partition = -1, change = 0;
        for (int i = n - 1; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
                partition = i - 1;
                break;
            }
        }
        if (partition != -1) {
            for (int i = n - 1; i > 0; i--) {
                if (nums[i] > nums[partition]) {
                    change = i;
                    break;
                }
            }
            swap(nums[partition], nums[change]);
        }
        reverse(nums.begin() + partition + 1, nums.end());

        return;
    }
};