题目描述:
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
思路：
参考下面文章：https://www.cnblogs.com/grandyang/p/4428207.html
class Solution {
public void nextPermutation(int[] nums) {
//1.先找到最后一个上升的位置
int pos = -1;
for(int i= nums.length-1; i>0 ; i--){
if(nums[i] > nums[i-1]){
pos = i-1;
break;
}
}
//2.如果没有这样的位置，那么说明此时序列已经是逆序的了，则把此序列逆序成最小的
if(-1==pos){
reverse(nums,0,nums.length-1);
return;
}
//3.存在，则找到pos之后，最后一个比他大的位置,然后交换两者
for(int i=nums.length-1; i>pos; i--){
if (nums[i] > nums[pos]) {
int tmp = nums[i];
nums[i] = nums[pos];
nums[pos] = tmp;
break;
}
}
reverse(nums,pos+1,nums.length-1);
}
public void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j]=tmp;
}
// 翻转数组
public void reverse(int[] arr, int start, int end) {
int l = start;
int r = end;
while (l < r) {
int tmp = arr[r];
arr[r] = arr[l];
arr[l] = tmp;
l++;
r--;
}
}
}
