LeetCode-31-下一个排列

31. 下一个排列

难度中等1151收藏分享切换为英文接收动态反馈

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

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

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

---

方法一：暴力法

最简单的想法就是暴力枚举，我们找出由给定数组的元素形成的列表的每个可能的排列，并找出比给定的排列更大的排列。

但是这个方法要求我们找出所有可能的排列，这需要很长时间，实施起来也很复杂。因此，这种算法不能满足要求。 我们跳过它的实现，直接采用正确的方法。

复杂度分析

时间复杂度：O(n!)，可能的排列总计有 n! 个。

空间复杂度：O(n)，因为数组将用于存储排列。

方法二：一遍扫描

首先，我们观察到对于任何给定序列的降序排列，就不会有下一个更大的排列。

例如，以下数组不可能有下一个排列：

[9, 5, 4, 3, 1]

这时应该直接返回升序排列。

所以对于一般的情况，如果有一个“升序子序列”，那么就一定可以找到它的下一个排列。具体来说，需要从右边找到第一对两个连续的数字 a[i] 和 a[i-1]，它们满足 a[i]>a[i-1]。

所以一个思路是，找到最后一个的“正序”排列的子序列，把它改成下一个排列就行了。

算法推导
如何得到这样的排列顺序？这是本文的重点。我们可以这样来分析：

我们希望下一个数比当前数大，这样才满足“下一个排列”的定义。因此只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。

我们还希望下一个数增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，我们需要：

1. 在尽可能靠右的低位进行交换，需要从后向前查找
2. 将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
3. 将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列

以上就是求“下一个排列”的分析过程。

以求 12385764 的下一个排列为例：

image-20210606181728260

首先从后向前查找第一个相邻升序的元素对 (i,j)。这里 i=4，j=5，对应的值为 5，7：

image-20210606181850859

然后在 [j,end) 从后向前查找第一个大于 A[i] 的值 A[k]。这里 A[i] 是 5，故 A[k] 是 6：

image-20210606181900770

将 A[i] 与 A[k] 交换。这里交换 5、6：

image-20210606181916299

这时 [j,end) 必然是降序，逆置 [j,end)，使其升序。这里逆置 [7,5,4]：

image-20210606181939830

因此，12385764 的下一个排列就是 12386457。

最后再可视化地对比一下这两个相邻的排列（橙色是蓝色的下一个排列）：

image-20210606181952049

// 思路：从后向前找到升序子序列，然后确定调整后子序列的最高位，剩余部分升序排列
public void nextPermutation1(int[] nums){
    int n = nums.length;

    // 1. 从后向前找到升序子序列，找到第一次下降的数，位置记为k
    int k = n - 2;
    while ( k >= 0 && nums[k] >= nums[k+1] )
        k --;

    // 找到k，就是需要调整部分的最高位

    // 2. 如果k = -1，说明所有数降序排列，改成升序排列
    if ( k == -1 ){
        Arrays.sort(nums);
        return;
    }

    // 3. 一般情况，k >= 0
    // 3.1 依次遍历剩余降序排列的部分，找到要替换最高位的那个数
    int i = k + 2;
    while ( i < n && nums[i] > nums[k] )
        i ++;

    // 当前的i，就是后面部分第一个比nums[k]小的数，i-1就是要替换的那个数

    // 3.2 交换i-1和k位置上的数
    int temp = nums[k];
    nums[k] = nums[i-1];
    nums[i-1] = temp;

    // 3.3 k之后的剩余部分变成升序排列，直接前后调换
    int start = k + 1;
    int end = n - 1;
    while ( start < end ){
        int tmp = nums[start];
        nums[start] = nums[end];
        nums[end] = tmp;
        start ++;
        end --;
    }
}

image-20210606182306939

// 降序数组翻转的操作提取出来
public void nextPermutation(int[] nums){
    int n = nums.length;

    // 1. 从后向前找到升序子序列，找到第一次下降的数，位置记为k
    int k = n - 2;
    while ( k >= 0 && nums[k] >= nums[k+1] )
        k --;

    // 找到k，就是需要调整部分的最高位

    // 2. 如果k = -1，说明所有数降序排列，改成升序排列
    if ( k == -1 ){
        reverse(nums, 0, n - 1);
        return;
    }

    // 3. 一般情况，k >= 0
    // 3.1 依次遍历剩余降序排列的部分，找到要替换最高位的那个数
    int i = k + 2;
    while ( i < n && nums[i] > nums[k] )
        i ++;

    // 当前的i，就是后面部分第一个比nums[k]小的数，i-1就是要替换的那个数

    // 3.2 交换i-1和k位置上的数
    swap(nums, k, i - 1);

    // 3.3 k之后的剩余部分变成升序排列，直接前后调换
    reverse(nums, k + 1, n - 1);
}

// 定义一个方法，交换数组中两个元素
private void swap( int[] nums, int i, int j ){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
// 定义一个翻转数组的方法
private void reverse( int[] nums, int start, int end ){
    while ( start < end ){
        swap(nums, start, end);
        start ++;
        end --;
    }
}

image-20210606183011344