31. 下一个排列
2022-02-27 10:22:00 # leecode

Link

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

Solution

参考来自：https://blog.csdn.net/QQ575787460/article/details/41215475

在当前序列中，从尾端往前寻找两个相邻元素，前一个记为 *i ，后一个记为 *ii ，并且满足 *i < *ii 。然后再从尾端寻找另一个元素 *j ，如果满足 *i < *j ，即将第 i 个元素与第 j 个元素对调，并将第 ii 个元素之后（包括 ii ）的所有元素颠倒排序，即求出下一个序列了。

首先，关于什么是全排列不做解释。如果一个排列为 A ，下一个排列为 A_NEXT ，那么 A_NEXT 一定与 A 有尽可能长的公共前缀。

看具体例子，一个排列为 124653 ，如何找到它的下一个排列，因为下一个排列一定与 124653 有尽可能长的前缀，所以，脑洞大开一下，从后面往前看这个序列，如果后面的若干个数字有下一个排列，问题就得到了解决。

第一步：找最后面 1 个数字的下一个全排列。
124653，显然最后 1 个数字 3 不具有下一个全排列。

第二步：找最后面 2 个数字的下一个全排列。
124653，显然最后 2 个数字 53 不具有下一个全排列。

第三步：找最后面 3 个数字的下一个全排列。
124653，显然最后 3 个数字 653 不具有下一个全排列。

——插曲：到这里相信大家已经看出来， 如果一个序列是递减的，那么它不具有下一个排列。

第四步：找最后面4个数字的下一个全排列。
124653，我们发现显然最后 4 个数字 4653 具有下一个全排列。因为它不是递减的，例如 6453 ， 5643 这些排列都在 4653 的后面。

我们总结上面的操作，并总结出重复上面操作的两种终止情况：
1：从后向前比较相邻的两个元素，直到前一个元素小于后一个元素，停止
2：如果已经没有了前一个元素，则说明这个排列是递减的，所以这个排列是没有下一个排列的。

124653 这个排列终止情况是上面介绍的第一种，从后向前比较相邻的 2 个元素，遇到 4<6 的情况停止。

并且我们可以知道：
1：124653 和它的下一个排列的公共前缀为 12 (因为 4653 存在下一个排列，所以前面的数字 12 保持不变)
2：4 后面的元素是递减的(上面介绍的终止条件是前一个元素小于后一个元素，这里是 4<6 )

现在，我们开始考虑如何找到4653的下个排列，首先明确4后面的几个数字中至少有一个大于4.

4 肯定要和 653 这 3 个数字中大于 4 的数字中 (6，5) 的某一个进行交换。这里就是 4 要和 6 ， 5 中的某一个交换，很明显要和 5 交换，如果找到这样的元素呢，因为我们知道 4 后面的元素是递减的，所以在 653 中从后面往前查找，找到第一个大于4的数字，这就是需要和4进行交换的数字。这里我们找到了 5 ，交换之后得到的临时序列为 5643 ，交换后得到的 643 也是一个递减序列。

所以得到的 4653 的下一个临时序列为 5643 ，但是既然前面数字变大了(4653—>5643)，后面的自然要变为升序才行，变换 5643 得到 5346 .

所以 124653 的下一个序列为 125643 .

Code

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
class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {5,1,1};
        solution.nextPermutation(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();
    }

    public void nextPermutation(int[] nums) {
        next_permutation(nums);
    }

    private boolean next_permutation(int[] p) {
        if (p.length == 1) return false;
        int i = p.length - 2;
        while (i >= 0 && p[i] >= p[i+1]) {
            --i;
        }
        if (i < 0){
            reverse(p, 0, p.length);
            return false;
        }
        for (int j = p.length-1; j >= 0; j--) {
            if (p[j] > p[i]) {
                int t = p[i];
                p[i] = p[j];
                p[j] = t;
                reverse(p, i+1, p.length);
                return true;
            }
        }
        return false;
    }

    private void reverse(int[] p, int l, int r) {
        for (r--; l<r; l++,r--) {
            int t = p[l];
            p[l] = p[r];
            p[r] = t;
        }
    }
}
Prev
2022-02-27 10:22:00 # leecode
Next