下一个排列
# 📃 题目描述
题目链接:31. 下一个排列 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须 原地 修改,只允许使用额外常数空间。
示例 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]
# 🔔 解题思路
这题感觉考的就是数学思维,反正我这种笨比不看答案是一个想法也蹦不出来(哭了)
我们希望下一个数比当前数大,这样才满足“下一个排列”的定义。⭐ 因此只需要将后面的「大数」与前面的「小数」交换,就能得到一个更大的数。比如 123456,将 5 和 6 交换就能得到一个更大的数 123465。
我们还希望下一个数增加的幅度尽可能的小,这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求,我们需要:
- 在尽可能靠右的低位进行交换,需要从后向前查找
- 将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465,下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
- 将「大数」换到前面后,需要将「大数」后面的所有数重置为升序,因为升序排列是最小的排列。以 123465 为例:首先按照上一步,交换 5 和 4,得到 123564;然后需要将 5 之后的数重置为升序,得到 123546。显然 123546 比 123564 更小,123546 就是 123465 的下一个排列
算法过程如下:
- 从后向前查找第一个相邻升序的元素对 (i,j),满足 A[i] < A[j]。此时 [j,end) 必然是降序
- 如果在步骤 1 找不到符合的相邻元素对,说明当前排列为降序排列,已经是最大数,则按照题意返回最小排列即直接逆置即可
- 在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k(也就是在 (i, end)中找到比 i 大的最小的一个数)。A[i]、A[k] 分别就是上文所说的「小数」、「大数」,将 A[i] 与 A[k] 交换
- 可以断定这时 [j,end) 必然是降序,逆置 [j,end),使其升序,这样获得的数字就是最小的
class Solution {
public void nextPermutation(int[] nums) {
// 1. 从后往前找第一个升序对 (nums[i], nums[i+1])
int i = nums.length - 2;
for (; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
break;
}
}
// 如果不存在升序对,说明当前排列已经是最大,直接反转即可
if (i == -1) {
reverseArray(nums, 0, nums.length - 1);
return ;
}
int j = i + 1;
// 2. 此时 [j, end] 一定是降序的,在 [j, end] 中找到比 nums[i] 大的数
// (或者说,从后往前 不超过 j 找到第一个比 nums[i] 大的数) 然后交换
for (int k = nums.length - 1; k >= j; k--) {
if (nums[k] > nums[i]) {
int temp = nums[k];
nums[k] = nums[i];
nums[i] = temp;
break;
}
}
// 3. 反转 [j, end] 为升序
reverseArray(nums, j, nums.length - 1);
}
// [left, right]
private void reverseArray(int[] nums, int left, int right) {
if (nums == null || nums.length == 0) {
return;
}
while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left ++;
right --;
}
}
}
# 💥 复杂度分析
- 空间复杂度:O(1)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10