Links

0031. 下一个排列

题目地址(31. 下一个排列)

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

题目描述

实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

前置知识

  • 回溯法

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

符合直觉的方法是按顺序求出所有的排列,如果当前排列等于 nums,那么我直接取下一个但是这种做法不符合 constant space 要求(题目要求直接修改原数组),时间复杂度也太高,为 O(n!),肯定不是合适的解。
我们也可以以回溯的角度来思考这个问题,即从后往前思考。
让我们先回溯一次,即思考最后一个数字是如何被添加的。
31.next-permutation-2
由于这个时候可以选择的元素只有 2,我们无法组成更大的排列,我们继续回溯,直到如图:
31.next-permutation-3
我们发现我们可以交换 4 和 2 就会变小,因此我们不能进行交换。
接下来碰到了 1。 我们有两个选择:
  • 1 和 2 进行交换
  • 1 和 4 进行交换
两种交换都能使得结果更大,但是 和 2 交换能够使得增值最小,也就是题目中的下一个更大的效果。因此我们 1 和 2 进行交换。
31.next-permutation-4
还需要继续往高位看么?不需要,因为交换高位得到的增幅一定比交换低位大,这是一个贪心的思想。
那么如何保证增幅最小呢? 其实只需要将 1 后面的数字按照从小到大进行排列即可。
注意到 1 后面的数已经是从大到小排列了(非严格递减),我们其实只需要用双指针交换即可,而不需要真正地排序。
1 后面的数一定是从大到小排好序了吗?当然,否则,我们找到第一个可以交换的回溯点就不是 1 了,和 1 是第一个可以交换的回溯点矛盾。因为第一个可以交换的回溯点其实就是从后往前第一个递减的值。

关键点解析

  • 写几个例子通常会帮助理解问题的规律
  • 在有序数组中首尾指针不断交换位置即可实现 reverse
  • 找到从右边起第一个大于nums[i]的,并将其和 nums[i]进行交换

代码

语言支持: Javascript, Python3, CPP
JavaScript Code:
/*
* @lc app=leetcode id=31 lang=javascript
*
* [31] Next Permutation
*/
function reverseRange(A, i, j) {
while (i < j) {
const temp = A[i];
A[i] = A[j];
A[j] = temp;
i++;
j--;
}
}
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var nextPermutation = function (nums) {
// 时间复杂度O(n) 空间复杂度O(1)
if (nums == null || nums.length <= 1) return;
let i = nums.length - 2;
// 从后往前找到第一个降序的,相当于找到了我们的回溯点
while (i > -1 && nums[i + 1] <= nums[i]) i--;
// 如果找了就swap
if (i > -1) {
let j = nums.length - 1;
// 找到从右边起第一个大于nums[i]的,并将其和nums[i]进行交换
// 因为如果交换的数字比nums[i]还要小肯定不符合题意
while (nums[j] <= nums[i]) j--;
const temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// 最后我们只需要将剩下的元素从左到右,依次填入当前最小的元素就可以保证是大于当前排列的最小值了
// [i + 1, A.length -1]的元素进行反转
reverseRange(nums, i + 1, nums.length - 1);
};
Python3 Code:
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = len(nums) - 1
while j >= 0 and nums[i] >= nums[j]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
left, right = i + 1, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
CPP Code:
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int i = nums.size() - 2, j = nums.size() - 1;
while (i >= 0 && nums[i] >= nums[i + 1]) --i;
if (i >= 0) {
while (j > i && nums[j] <= nums[i]) --j;
swap(nums[i], nums[j]);
}
reverse(nums.begin() + i + 1, nums.end());
}
};

相关题目