友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
31. 下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
-
例如，
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：
输入：nums = [1,2,3] 输出：[1,3,2]
示例 2：
输入：nums = [3,2,1] 输出：[1,2,3]
示例 3：
输入：nums = [1,1,5] 输出：[1,5,1]
提示：
-
1 <= nums.length <= 100 -
0 <= nums[i] <= 100
思路分析
可以看成寻找下一个更大的数。这样更容易理解。
标准的 “下一个排列” 算法可以描述为：
-
从后向前 查找第一个 相邻升序 的元素对
(i,j)，满足A[i] < A[j]。此时[j,end)必然是降序 -
在
[j,end)从后向前 查找第一个满足A[i] < A[k]的k。A[i]、A[k]分别就是上文所说的「小数」、「大数」 -
将
A[i]与A[k]交换 -
可以断定这时
[j,end)必然是降序，逆置[j,end)，使其升序 -
如果在步骤 1 找不到符合的相邻元素对，说明当前
[begin,end)为一个降序顺序，则直接跳到步骤 4
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-10-22 18:22:39
*/
public void nextPermutation(int[] nums) {
int len = nums.length;
for (int i = len - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) { //找到小数
//重新找一个较大的数，可能是之前的i+1,也可能不是，
for (int j = len - 1; j > i; j--) {
//最差可能就是i+1，最好是尽量靠右的
if (nums[j] > nums[i]) {
swap(nums, i, j);
//i从最小，换为右边较大的数，然后后面开始逆置
reverse(nums, i + 1, len - 1);
return;
}
}
}
}
reverse(nums, 0, len - 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
//由于nums[i] < nums[i+1]，我们可以知道，到满足这个条件的前提，是必须存在递增，
//从后面往前，遍历了很多个才碰到第一个符合条件的，
//那么说明从第一个符合条件开始往后，后面的肯定都是递减，是降序的，所以逆置即可最快重新排序。
private void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-21 15:29:48
*/
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
// 选择第一对升序数字，是降序就向前走。
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
// 如果找到了升序数字对，则从后向前寻找一个大于 nums[i] 的数字，然后交换
int j = nums.length - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
swap(nums, i, j);
}
// 反转 i+1 的数字
reverse(nums, i + 1);
}
private void reverse(int[] nums, int index) {
int left = index, right = nums.length - 1;
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}