LeetCode 31. 下一个排列

题目描述

🔥 31. 下一个排列

image-20230305171846186

思路分析

  1. 从右向左遍历数组，找到第一个相邻的数字对 (i, i+1)，满足 nums[i] < nums[i+1]。
  2. 如果找到了这样的数字对，再次从右向左遍历数组，找到第一个数字 j，满足 nums[j] > nums[i]。
  3. 交换 nums[i] 和 nums[j]。
  4. 将从 i+1 开始到数组末尾的部分进行翻转，使其变成升序。
  5. 如果步骤 1 中没有找到数字对，说明整个数组已经是最大排列，直接翻转整个数组。
1
2
3

步骤 1：1 3 5 4 2
步骤 2：1 4 5 3 2
步骤 3：1 4 2 3 5

image-20230305192649898

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

func nextPermutation(nums []int) {
	if len(nums) <= 1 {
		return
	}
	i := len(nums) - 2
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}
	if i >= 0 {
		j := len(nums) - 1
		for nums[j] <= nums[i] {
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	left, right := i+1, len(nums)-1
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
}

考虑序列 [1, 3, 5, 4, 2]，我们可以按照以下步骤找到下一个排列：

  1. 从右向左找到第一个相邻数字对 (3, 5)，满足 3 < 5，此时 i = 1。
  2. 从右向左找到第一个大于 3 的数字，是 4，将其与 3 交换，序列变为 [1, 4, 5, 3, 2]。
  3. 对从位置 i+1 开始的部分 [5, 3, 2] 进行翻转，得到 [1, 4, 2, 3, 5]，这就是下一个排列。

在这个示例中，我们从逻辑上解释了代码的每个步骤，说明了如何找到下一个排列并进行交换和翻转。

🍏 点击查看 Java 题解

1

write your code here

相似题目

题目 难度 题解
全排列 Medium  
全排列 II Medium  
排列序列 Hard  
回文排列 II Medium  
本文作者:
本文链接: https://hgnulb.github.io/blog/86157839
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！