1，问题描述
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：
1
2
| 输入：nums = [1,2,3]
输出：[1,3,2]
|
示例 2：
1
2
| 输入：nums = [3,2,1]
输出：[1,2,3]
|
示例 3：
1
2
| 输入：nums = [1,1,5]
输出：[1,5,1]
|
提示：
1 <= nums.length <= 1000 <= nums[i] <= 100
2，初步思考
第一次解答时，把问题想简单了，没解决处理
第二次使用了额外的空间进行解答，时间复杂度O(n)、空间复杂度O(n)，但其实这个解答不符合题目要求得空间复杂度
第三次，在方法二的基础上不使用额外的空间，双指针的解法，时间复杂度O(n^2)，空间复杂度O(1)
3，代码处理
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
| import java.util.ArrayList;
import java.util.List;
public class _31下一个排列 {
public void nextPermutation(int[] nums) {
int max = Integer.MIN_VALUE;
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] < max) {
int j = i + 1;
for (; j < nums.length; j++) {
if (nums[j] > nums[i]) {
swap(nums, i, j);
break;
}
}
return;
} else {
max = nums[i];
indexBubbleSort(nums, i);
}
}
}
private void indexBubbleSort(int[] nums, int start) {
for (int i = start; i < nums.length - 1; i++) {
swap(nums, i, i + 1);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void nextPermutation_area(int[] nums) {
List<Integer> list = new ArrayList<>();
int i = nums.length - 1;
boolean flag = true;
for (; i >= 0 && flag; i--) {
list.add(nums[i]);
if (i != 0 && nums[i] > nums[i - 1]) {
int before = nums[i - 1];
int next = 0;
for (int j = 0; j < list.size() && flag; j++) {
next = list.get(j);
if (next > nums[i - 1]) {
list.remove(j);
list.addFirst(before);
flag = false;
}
}
nums[i - 1] = next;
}
}
singleBubleSort(list);
for (int j = 0; j < list.size(); j++) {
nums[i + j + 1] = list.get(j);
}
}
public void singleBubleSort(List<Integer> arr) {
for (int i = 0; i < arr.size() - 1; i++) {
if (arr.get(i) < arr.get(i + 1)) return;
int temp = arr.get(i);
arr.set(i, arr.get(i + 1));
arr.set(i + 1, temp);
}
}
public void nextPermutation_fail(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
for (int i = nums.length - 1; i > 0; i--) {
if (nums[i] > nums[i - 1]) {
int pre = nums[i - 1];
nums[i - 1] = nums[i];
nums[i] = pre;
return;
}
}
reverse(nums);
}
private void reverse(int[] nums) {
if (nums == null || nums.length <= 1) return;
int l = 0;
int r = nums.length - 1;
while (l < r) {
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
l++;
r--;
}
}
public static void main(String[] args) {
_31下一个排列 nextPermutation = new _31下一个排列();
int[] ints = {1, 5, 8, 4, 7, 6, 5, 3, 1};
nextPermutation.nextPermutation(ints);
for (int anInt : ints) {
System.out.println(anInt);
}
}
}
|
官方题解中速度最快的解法，本质与stack栈一致
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
| class Solution {
public boolean isValid(String s) {
char[] s1 = s.toCharArray();
int[] ss = new int[s.length()];
int top = -1,n = s.length();
for(int i = 0;i < n;i ++){
if(s1[i] == '(' || s1[i] == '{' || s1[i] == '['){
ss[++ top] = s1[i];
}
else{
if(s1[i] == ')'){
if(top == -1 || ss[top] != '(')
return false;
top --;
}
else if(s1[i] == '}'){
if(top == -1 || ss[top] != '{')
return false;
top --;
}
else if(s1[i] == ']'){
if(top == -1 || ss[top] != '[')
return false;
top --;
}
}
}
return top == -1;
}
}
|
4，其他
一定要先把题目的限制、要解决什么问题先搞懂，别着急上手