LeetCode 31. 下一个排列

Categories:

Tags:

题目描述
思路分析
具体步骤解析
参考代码

题目描述

🔥 31. 下一个排列

思路分析

要找到下一个排列，我们可以遵循以下步骤：

从后向前查找第一个不满足递增顺序的元素：

从数组的末尾开始，寻找第一个元素 nums[i]，使得 nums[i] < nums[i + 1]。这个元素的索引 i 表示我们需要进行调整的部分。

如果找不到这样的 i，说明当前排列是最大的排列，直接反转整个数组即可。

找到替换元素：

接下来，从数组的末尾再次查找，找到第一个大于 nums[i] 的元素 nums[j]。这个元素是我们要替换的元素。

交换：

交换 nums[i] 和 nums[j]，这样可以使得排列变得更大。

反转后面的元素：

最后，将 nums[i + 1] 到 nums[n - 1] 的部分反转，以得到下一个排列。

具体步骤解析

下面以数组 [1, 3, 5, 4, 2] 为例，详细说明如何找到下一个排列。

首先，初始数组为：[1, 3, 5, 4, 2]

接下来，我们从后向前查找第一个不满足递增顺序的元素。我们从数组的末尾开始，寻找第一个元素 nums[i]，使得 nums[i] < nums[i + 1]。这个元素的索引 i 表示我们需要进行调整的部分。

从后向前查找：

i = 4，nums[4] = 2，nums[3] = 4，2 < 4，继续。

i = 3，nums[3] = 4，nums[2] = 5，4 < 5，继续。

i = 2，nums[2] = 5，nums[1] = 3，5 > 3，停止。

我们找到 i = 1，即 nums[1] = 3。

接下来，我们从数组的末尾再次查找，找到第一个大于 nums[i] 的元素 nums[j]。这个元素是我们要替换的元素。

从后向前查找，找到第一个大于 nums[i] 的元素：

j = 4，nums[4] = 2，2 <= 3，继续。

j = 3，nums[3] = 4，4 > 3，停止。

我们找到 j = 3，即 nums[3] = 4。

然后，我们交换 nums[i] 和 nums[j]：[1, 3, 5, 4, 2] --> [1, 4, 5, 3, 2]

最后，我们需要反转 nums[i + 1] 到末尾的元素。我们反转 nums[2] 到 nums[4]，即 [5, 3, 2] 反转为 [2, 3, 5]：[1, 4, 5, 3, 2] --> [1, 4, 2, 3, 5]

经过以上步骤，数组 [1, 3, 5, 4, 2] 的下一个排列为：[1, 4, 2, 3, 5]

参考代码

// 下一个排列函数
func nextPermutation(nums []int) {
	n := len(nums)
	if n <= 1 {
		return
	}

	// 步骤 1: 从后向前找到第一个不满足递增顺序的元素
	i := n - 2
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}

	// 步骤 2: 如果找到了这样的元素
	if i >= 0 {
		// 步骤 3: 找到第一个大于 nums[i] 的元素
		j := n - 1
		for nums[j] <= nums[i] {
			j--
		}
		// 交换
		nums[i], nums[j] = nums[j], nums[i]
	}

	// 步骤 4: 反转 i 之后的部分
	reverse(nums, i+1, n-1)
}

func reverse(nums []int, start int, end int) {
	for start < end {
		nums[start], nums[end] = nums[end], nums[start]
		start++
		end--
	}
}

时间复杂度：O (n)，其中 n 是数组的长度。我们只需遍历数组几次。

空间复杂度：O (1)，我们只使用了常数级别的额外空间。

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/86157839