实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解释思路
从后往前遍历数组，找到第一个小于当前索引位置的数，假设当前索引是$i$，则找到$i-1$，有以下三种情况：
1.$i==nums.length$，说明数组是一个升序数组，直接交换$nums[i]$和$nums[i-1]$的位置即可，如$123$->$132$
2.$0<i<nums.length$，说明这样的数在数组中间，直接从第$[i…nums.length]$的数中找到一个大于且仅大于$nums[i-1]$的数，即这个数是$[i…nums.length]$中大于$nums[i-1]$中最小的，假设该索引是$min$，然后交换$nums[i-1]$和$nums[min]$的值，并将$[i…nums.length]$中的所有数进行升序排序，便是最终答案
3.$i==0$，说明数组是一个倒序的数组，直接将数组$reverse$即可。
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
| class Solution {
public void nextPermutation(int[] nums) {
if (nums.length == 1)
return;
int i = nums.length - 1;
for (; i > 0; i--) {
if (nums[i] <= nums[i - 1]) continue;
if (i == nums.length - 1) {
nums[i] = nums[i - 1] ^ nums[i];
nums[i - 1] = nums[i - 1] ^ nums[i];
nums[i] = nums[i - 1] ^ nums[i];
return;
}
int min = i;
for (int j = nums.length - 1; j >= i; j--) {
if (nums[j] > nums[i - 1] && nums[j] < nums[min])
min = j;
}
nums[i- 1] = nums[i - 1] ^ nums[min];
nums[min] = nums[i - 1] ^ nums[min];
nums[i- 1] = nums[i - 1] ^ nums[min];
for (int j = i; j < nums.length - 1; j++) {
for (int k = i; k < nums.length - 1; k++) {
if (nums[k] > nums[k + 1]) {
nums[k] = nums[k] ^ nums[k + 1];
nums[k + 1] = nums[k] ^ nums[k + 1];
nums[k] = nums[k] ^ nums[k + 1];
}
}
}
return;
}
int l = 0, r = nums.length - 1;
while (l < r) {
nums[l] = nums[l] ^ nums[r];
nums[r] = nums[l] ^ nums[r];
nums[l] = nums[l] ^ nums[r];
l ++;
r --;
}
}
}
|
