下一个排列
题目描述
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
思路
下一个排列，就是找出字典序大的下一个
所以从后往前比较，出现了变小的情况index，就说明index与后面任一一个比nums[index]大的交换，字典序都比原来的大
那要刚刚好大一个，所以要和从后往前第一个比它大的交换，（因为index右都是递减的）
交换完毕后在index后，从小到大sort排序即可。
特殊情况是原序列就是递减的，所以直接sort即可
Java实现
public void nextPermutation(int[] nums) {
boolean flag=false;
int index=0;
for(int i=nums.length-2;i>=0;i--){
if(nums[i]<nums[i+1]){
index=i;
break;
}
if(i==0){
flag=true;
}
}
if(flag==true){
Arrays.sort(nums);
return;
}
for(int i=nums.length-1;i>index;i--){
if(nums[i]>nums[index]){
nums[i]^=nums[index];
nums[index]^=nums[i];
nums[i]^=nums[index];
Arrays.sort(nums,index+1,nums.length);
return;
}
}
}
执行用时 :2 ms, 在所有 Java 提交中击败了79.11%的用户
内存消耗 :37.1 MB, 在所有 Java 提交中击败了88.39%的用户
