題目
Implement next permutation,
which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible,
it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples.
Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
分析
題目要求是給出一個數(shù)字排列中按字典序排列的下一個更大的排列悍缠。如果沒有更大的則給出最小的搅裙，比如1,2,3->1,3,2下一個字典序更大的排列是1,3,2掂林，而3,2,1是最大的字典序排列志鞍，修改為最小的1,2,3。
解這道題可以通過觀察家乘，1,4,3,2 -> 2,1,3,4分為三步：
- 逆向?qū)ふ业降谝粋€非遞減的數(shù)nums[i] < nums[i+1]
- 將這個數(shù)與后面最后一個比它大的數(shù)調(diào)換（僅大于它）蝗羊，不能找最后一個，因?yàn)樽詈笠粋€不一定大于它烤低。
- 將這個數(shù)后面重新排序,讓后面的數(shù)最小
這樣看第一步找到1肘交，第二步將1與2調(diào)換得到2,4,3,1，第三步將2后面的4,3,1排序扑馁，得到2,1,4,3
需要注意的是涯呻，如果這個序列全部遞減（最大），則直接重新排序即得到最小序列
這個方法的原始出處在這里
復(fù)雜度分析
最多對數(shù)組進(jìn)行了3次掃描腻要，時間復(fù)雜度為O(n)复罐，空間復(fù)雜度為O(1)
代碼
public void nextPermutation(int[] nums) {
if(nums == null || nums.length <= 1) return;
int i = nums.length - 2;
for(; i >= 0 && nums[i] >= nums[i+1]; --i); //第一步
if(i >= 0){ //否則全部都是遞減的，不需要調(diào)換了
int j = i+1;
for(; j < nums.length && nums[j] > nums[i]; ++j); //這里是大于雄家，不能加等于
swap(nums, i, j - 1); //第二步
}
int j = nums.length - 1; //因?yàn)楹竺婵隙ㄊ悄嫘虻男ё纾灾苯觾牲c(diǎn)調(diào)換即可
for(i = i + 1; i < j; i++,j--){
swap(nums, i, j);
}
}
public void swap(int[] nums, int index1, int index2){
int i = nums[index1];
nums[index1] = nums[index2];
nums[index2] = i;
}
