-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathArray31.java
More file actions
71 lines (66 loc) · 2 KB
/
Array31.java
File metadata and controls
71 lines (66 loc) · 2 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package array;
import java.util.Arrays;
/**
* @ProjectName: leetcode
* @Package: array
* @ClassName: Array31
* @Author: markey
* @Description:31. 下一个排列
* 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
*
* 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
*
* 必须原地修改，只允许使用额外常数空间。
*
* 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
* 1,2,3 → 1,3,2
* 3,2,1 → 1,2,3
* 1,1,5 → 1,5,1
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/next-permutation
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* @Date: 2020/5/3 19:37
* @Version: 1.0
*/
public class Array31 {
public void nextPermutation(int[] nums) {
getNextPermutation(nums);
}
public static void getNextPermutation(int[] nums) {
int max = Integer.MIN_VALUE;
int maxJ = -1;
int index = nums.length - 1;
while( index >= 0){
if( maxJ != -1 && max > nums[index] ){
int minMax = findMinMax(nums,index);
swap(nums,index,minMax);
break;
}
if( nums[index] >= max ){
max = nums[index];
maxJ = index;
}
index--;
}
if( index != -1){
Arrays.sort(nums,index+1,nums.length);
}else {
Arrays.sort(nums);
}
}
private static int findMinMax(int[] nums, int index) {
Arrays.sort(nums,index+1,nums.length);
for (int i = index+1; i < nums.length; i++) {
if( nums[i] > nums[index] ){
return i;
}
}
return -1;
}
public static void swap(int[] nums,int l ,int r){
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
}
}