題目描述:
實(shí)現(xiàn)獲取下一個(gè)排列的函數(shù)倦微，算法需要將給定數(shù)字序列重新排列成字典序中下一個(gè)更大的排列。
如果不存在下一個(gè)更大的排列，則將數(shù)字重新排列成最小的排列（即升序排列）蹂窖。
必須原地修改，只允許使用額外常數(shù)空間恩敌。
以下是一些例子瞬测，輸入位于左側(cè)列，其相應(yīng)輸出位于右側(cè)列纠炮。
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.先找到最后一個(gè)上升的位置
int pos = -1;
for(int i= nums.length-1; i>0 ; i--){
if(nums[i] > nums[i-1]){
pos = i-1;
break;
}
}
//2.如果沒有這樣的位置月趟，那么說明此時(shí)序列已經(jīng)是逆序的了，則把此序列逆序成最小的
if(-1==pos){
reverse(nums,0,nums.length-1);
return;
}
//3.存在恢口，則找到pos之后孝宗，最后一個(gè)比他大的位置,然后交換兩者
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;
}
// 翻轉(zhuǎn)數(shù)組
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--;
}
}
}
