31. 下一个排列

🟠   🔖  数组 双指针  🔗 LeetCode

题目

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be [in place](http://en.wikipedia.org/wiki/In- place_algorithm) and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]

Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]

Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]

Output: [1,5,1]

Constraints:

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

题目大意

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
• 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
• 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

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

解题思路

1. 从后往前找到第一个下降点：
   • 从右向左扫描数组，找到第一个破坏升序的元素，也就是说，找到第一个位置 i，使得 nums[i] < nums[i + 1]。这个位置 i 及其之前的元素是无法变得更大的，而我们可以通过调整 i 之后的元素来得到下一个更大的排列。
2. 在 i 之后找到比 nums[i] 大的最小元素：
   • 继续从右向左扫描，找到第一个比 nums[i] 大的元素 nums[j]。交换 nums[i] 和 nums[j]，这样可以确保得到比当前排列大的下一个排列。
3. 将 i 之后的元素翻转：
   • 由于 i 之后的部分是降序排列的（因为我们从后向前扫描），我们需要将这部分反转，变成升序排列，以获得字典序中下一个更大的排列。
4. 特殊情况：
   • 如果整个数组是降序排列的，比如 [3, 2, 1]，那么我们已经处于字典序的最大排列，此时直接将整个数组反转为升序排列即可。

以数组 [1, 2, 3, 4] 为例：

1. 从后往前找到第一个下降点：

   • 从右向左看，3 < 4，因此 i = 2（nums[2] = 3）。

2. 找到比 3 大的最小数：

   • 从右向左看，4 是比 3 大的最小数，所以 j = 3（nums[3] = 4）。
   • 交换 nums[i] 和 nums[j]，即 nums[2] 和 nums[3] 交换，数组变为：[1, 2, 4, 3]

3. 反转 i 之后的部分：

   • 现在 i = 2，i 之后的部分是 [3]。由于反转单个元素没有任何变化，所以反转后仍然是 [3]。

经过这三个步骤后，数组 [1, 2, 3, 4] 的下一个排列是： [1, 2, 4, 3]

复杂度分析：

• 时间复杂度：O(n)，其中 n 是数组的长度。我们从右向左扫描数组，最多扫描两次（一次找到下降点，一次找到交换点），然后再翻转一部分数组，所以整体复杂度是线性时间。
• 空间复杂度：O(1)，因为只需要常数个额外的变量进行原地交换和反转操作，没有使用额外的数组。

代码

var nextPermutation = function (nums) {
	let i = nums.length - 2;

	// 从右向左找到第一个下降点
	while (i >= 0 && nums[i] >= nums[i + 1]) {
		i--;
	}

	if (i >= 0) {
		// 说明找到了第一个下降点
		let j = nums.length - 1;
		// 找到第一个比 nums[i] 大的数
		while (j >= 0 && nums[j] <= nums[i]) {
			j--;
		}
		// 交换 i 和 j 位置上的数
		[nums[i], nums[j]] = [nums[j], nums[i]];
	}

	// 翻转 i 之后的部分，使其变为升序
	let left = i + 1;
	let right = nums.length - 1;
	while (left < right) {
		[nums[left], nums[right]] = [nums[right], nums[left]];
		left++;
		right--;
	}
};

相关题目

题号	标题	题解	标签	难度
46	全排列	[✓]	数组 回溯
47	全排列 II	[✓]	数组 回溯
60	排列序列		递归 数学
267	回文排列 II		哈希表 字符串 回溯
1850	邻位交换的最小次数		贪心 双指针 字符串