实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列(即,组合出下一个更大的整数)。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须 原地 修改,只允许使用额外常数空间。
示例 1:
输入:nums = [1,2,3]
输出:[1,3,2]
示例 2:
输入:nums = [3,2,1]
输出:[1,2,3]
示例 3:
输入:nums = [1,1,5]
输出:[1,5,1]
示例 4:
public void nextPermutation(int[] nums) {
int n = nums.length;
//找到突然下降的位置
int k = n - 2;
//找到的k就是需要调整部分的最高位
while (k >= 0 && nums[k] >= nums[k + 1]) k --;
//如果k = -1 所有数字降序,改为升序
if (k == -1) {
Arrays.sort(nums);
return;
}
//一般情况,k >= 0
//找到第一个比nums[k]小的数字,i - 1 为替换的那个数字
int i = k + 2;
while (i < n && nums[i] > nums[k]){
i ++;
}
//交换
int temp = nums[k];
nums[k] = nums[i - 1];
nums[i - 1] = temp;
//k之后的数字变为升序
int start = k + 1;
int end = n - 1;
while (start < end){
int tmp = nums[start];
nums[start] = nums[end];
nums[end] = tmp;
start ++;
end --;
}
}