LeetCode-31-下一个排列
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 <= 1000 <= 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。
我们还希望下一个数增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，我们需要：
- 在尽可能靠右的低位进行交换，需要从后向前查找
- 将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
- 将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列。以 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
