class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
if(n < 2) return;
for(int i=n-1; i >= 1; i--){
if(nums[i] > nums[i-1]){
// (i, n) 是降序 这里是因为之前循环是从后往前寻找,前一个比自己小的,直到找到这里,所以(i, n) 是降序
// 在(i+1, n)的区间内寻找最后一个大于nums[i]的值(也就是找到最小的比)
int j = i;
for(int k=i+1; k < n; k++){
if(nums[k] > nums[i-1]){
j = k;
}
}
// 交换 i 之后大于nums[i-1]的元素
swap(nums, i-1, j);
// 将 (i, n) 升序排序
// 因为(i, n) 是降序, 所以这里用快排有点慢
Arrays.sort(nums, i, n);
return;
}
}
// 本身是最后一个排列, 则初始化为第一个升序序列
Arrays.sort(nums);
}
// 交换元素
public void swap(int[] arr, int x, int y){
arr[x] = arr[x] ^ arr[y];
arr[y] = arr[x] ^ arr[y];
arr[x] = arr[x] ^ arr[y];
}
}
参考转载:
链接:https://leetcode.cn/problems/next-permutation/solutions/80560/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/
来源:力扣(LeetCode)