## Tuesday, November 25, 2014

### [LeetCode] Next Permutation

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`

7 2 5 2 3 1
7 2 5 3 1 2
7 2 5 3 2 1
7 3 1 2 2 5

1. 从低位向高位（从右向左）找第一个递减的数：s[i]<s[i+1]。如果不存在，则表明该permutation已经最大，next permutation为当前序列的逆序。
2. 在s[i+1:n-1]中找一个j，使s[j]>s[i]>=s[j+1]，swap(s[i], s[j])
3. 将s[i+1:n-1]排序，从低位到高位单调递减。

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20``` ```class Solution { public: void nextPermutation(vector &num) { if(num.size()<2) return; int n = num.size(), j = n-2; while(j>=0 && num[j]>=num[j+1]) j--; if(j<0) { sort(num.begin(),num.end()); return; } int i=j+1; while(inum[j]) i++; i--; swap(num[i],num[j]); sort(num.begin()+j+1, num.end()); } }; ```

#### 2 comments:

1. 最后是不需要sort的，因为换过去之后，后面已经是按降序排列了，所以直接reverse就可以了。

2. 最后是不需要sort的，因为换过去之后，后面已经是按降序排列了，所以直接reverse就可以了。