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
思路：
這道題讓我們求下一個(gè)排列順序风秤，有題目中給的例子可以看出來(lái)对湃，如果給定數(shù)組是降序澎语，則說(shuō)明是全排列的最后一種情況杜恰，則下一個(gè)排列就是最初始情況，可以參見(jiàn)之前的博客 Permutations 全排列。我們?cè)賮?lái)看下面一個(gè)例子，有如下的一個(gè)數(shù)組
1 2 7 4 3 1
下一個(gè)排列為：
1 3 1 2 4 7
那么是如何得到的呢悼粮，我們通過(guò)觀察原數(shù)組可以發(fā)現(xiàn)，如果從末尾往前看曾棕，數(shù)字逐漸變大扣猫，到了2時(shí)才減小的，然后我們?cè)購(gòu)暮笸罢业谝粋€(gè)比2大的數(shù)字翘地，是3申尤，那么我們交換2和3，再把此時(shí)3后面的所有數(shù)字轉(zhuǎn)置一下即可衙耕，步驟如下：
1 2 7 4 3 1
1 2 7 4 3 1
1 3 7 4 2 1
1 3 1 2 4 7
var nextPermutation = function(nums) {
var i,j,n=nums.length;
for(var i=n-2;i>=0;--i){
if(nums[i+1]>nums[i]){
for(var j=n-1;j>=i;j--){
if(nums[j]>nums[i]) break;
}
var tmp=nums[i];
nums[i]=nums[j];
nums[j]=tmp;
nums=nums.slice(0,i+1).concat(nums.slice(i+1).reverse());
//console.log(nums)
return;
}
}
nums.reverse();
};
