题目描述
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
示例一：
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
思路
1.其实本题中的下一个排列就是比当前数大的下一个数。
2.我们首先应该找到那对应该被交换的数字。
3.左边应该被交换的数字符合nums[i]<nums[i-1]的特征；右边应该被交换的数是刚好大于左边数字的最小数字，即j in (i+1,nums.length-1) && min(i+1,nums.length-1) && nums[j]>nums[i]。
4.我们交换数据后，将左边数字的右边进行从小到大排序即可。
例如：
1587624310
1.找到 2 为左边应该被交换位置的数
2.找到 3 为右边应该被交换位置的数
3.交换 2 和 3 的位置--->1587634210
4.升序排序 3 右边的数字 ---->1587630124
Java代码实现
public void nextPermutation(int[] nums) {
int i = nums.length-2;
//寻找左边的数
while(i>=0 && nums[i]>=nums[i+1]){
i--;
}
//寻找右边的数
if(i>=0){
int j = nums.length-1;
while(nums[j]<=nums[i]){
j--;
}
swap(nums,i,j);
}
//因为右边的数交换完成后是降序的，所以直接翻转即可
reverseNums(nums,i+1,nums.length-1);
}
private void reverseNums(int[] nums,int left,int right){
while(left<right){
swap(nums,left++,right--);
}
}
private void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
