-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathSolution0031.java
More file actions
47 lines (44 loc) · 2.43 KB
/
Copy pathSolution0031.java
File metadata and controls
47 lines (44 loc) · 2.43 KB
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
41
42
43
44
45
46
47
// 31. 下一个排列
/*
1、“下一个排列”定义：
1）给定数字序列的字典序中下一个更大的排列。可以理解成这些数字拼凑成的多个整数，升序排序，然后求当前整数的下一个整数
2）如果不存在下一个更大的排列，则将数字重新排列成最小的排列。即整数是最大的，那么整体升序排列得到一个最小的整数
2、算法推导
1）我们希望下一个数比当前数大，这样才满足“下一个排列”的定义。因此只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数
2）我们还希望下一个数增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，需要：
① 在尽可能靠右的低位进行交换，需要从后向前查找
② 将一个尽可能小的「大数」与前面的「小数」交换
③ 将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列
3、算法过程
1）从后向前查找第一个相邻升序的元素对 (i-1,i)，满足 A[i-1] < A[i]，即找到第一个可交换的最低位「小数」。此时 [i,end) 必然是降序
2）在 [i,end) 从后向前查找第一个满足 A[i-1] < A[j] 的 j，即找到第一个可交换的值最小的「大数」。A[i-1]、A[j] 分别是「小数」、「大数」
3）将 A[i-1] 与 A[j] 交换
4）此时 [i,end) 必然是降序，逆置 [i,end)，使其升序
5）如果在步骤1找不到符合的相邻升序元素对，说明当前 [0,end) 为一个降序顺序，即最大的排序，则整体升序得到最小的排列
1 2 3 8 5 7 6 4
↑ ↑ ↑
i-1 i j
1 2 3 8 6 4 5 7
*/
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
if (n <= 1) {
return;
}
for (int i = n - 1; i >= 1; i--) {
if (nums[i] > nums[i - 1]) {
for (int j = n - 1; j >= i; j--) {
if (nums[j] > nums[i - 1]) {
int temp = nums[j];
nums[j] = nums[i - 1];
nums[i - 1] = temp;
Arrays.sort(nums, i, n);
return;
}
}
}
}
Arrays.sort(nums);
}
}