实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列(即,组合出下一个更大的整数)。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须 原地 修改,只允许使用额外常数空间。
解析:
找到输入数组字典序中的下一个位置,感觉像是找规律一样..... (可以多举几个例子,找一下其中的共同点) 比如1,2,3,4,5的下一个字典序为1,2,3,5,4 可以看到只改变了最后两个数字,因为整个序列都是升序的
再比如1,5,4,3,2的下一个字典序为2,5,4,3,1 可以看到5,4,3,2是降序的,就需要找到比1的大的最小数字2,和1交换位置,然后后面的升序排序
于是,从中总结出规律,需要先找到左右两个下标left和right,left表示最后一组的升序数字的第1个,right表示left后面的数字中比l大的最靠右的数字,比如
1,2,3,4,5 -> left = 4 , right = 5
1,5,4,3,2 -> left = 1 , right= 2
然后,将left和right位置的数字交换,交换后,对left后面部分的数字进行升序排序即可
Java:
class Solution {
public void nextPermutation(int[] nums) {
int left = 0, right = nums.length - 1;
for(int i = 0; i < nums.length - 1; i++) {
if(nums[i] < nums[i + 1]) {
left = i;
}
}
for(int i = left + 1; i < nums.length; i++) {
if(nums[i] > nums[left]) {
right = i;
}
}
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
Arrays.sort(nums, left + 1, nums.length);
return;
}
}
JavaScript:
var nextPermutation = function(nums) {
let left = 0, right = nums.length - 1;
for(let i = 0; i < nums.length - 1; i++) {
if(nums[i] < nums[i + 1]) {
left = i;
}
}
for(let i = 0; i < nums.length; i++) {
if(nums[i] > nums[left]) {
right = i;
}
}
let temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
let arr = nums.slice(left+1);
arr.sort((a,b) => a - b);
nums.splice(left+1,nums.length - left, ...arr);
return;
};