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

這一題的時間複雜度是O(n)。 解題思路：

從後往前找，m,j,i,l, ， 如果num[i] > num[i + 1], 即 一直是倒序，則繼續往前找， 直到找個一個num[i]< num[i + 1]的， 即第一個比它右邊小的數字。 

這是因為如果 從後往前一直是倒序，則已經是permutation了 不可能出現更大的， 隻有順序反了的那個地方才是需要動的地方。

接着将這個數字num[i] , 和它右邊的數字比較，找個一個剛好比他大一點的數字， 兩者替換位置。 接着再将i 之後的數字排序，正序，即可。

1 public class Solution {
 2     public void nextPermutation(int[] num) {
 3         // Start typing your Java solution below
 4         // DO NOT write main() function
 5         int j,i;
 6         for(i = num.length - 1; i > 0; i --){
 7             j = i - 1;
 8             if(num[j] < num[i]){
 9                 int ex = 0;
10                 int a;
11                 for(a = i; a < num.length; a ++){
12                     if(num[a] > num[j]){
13                         ex = num[a];
14                     }
15                     else{
16                         break;
17                     }
18                 }
19                 num[a - 1] = num[j];
20                 num[j] = ex;
21                 for(int ii = i; ii < (num.length - i) / 2 + i; ii ++){
22                     int cur = num[ii];
23                     num[ii] = num[num.length - ii - 1+ i];
24                     num[num.length - ii- 1 + i] = cur;
25                 }
26                 return;
27             }
28         }
29         for(i = 0; i < num.length / 2; i ++){
30             int cur = num[i];
31             num[i] = num[num.length - 1 - i];
32             num[num.length - 1 - i] = cur;
33         }
34     }
35 }      

1 public class Solution {
 2     public void nextPermutation(int[] num) {
 3         if(num == null || num.length < 2) return;
 4         int len = num.length;
 5         int point = -1;
 6         for(point = len - 2; point > -1; point --){
 7             if(num[point] < num[point + 1]) break;
 8         }
 9         if(point == -1){
10             for(int i = 0; i < num.length / 2; i ++){
11                 int cur = num[i];
12                 num[i] = num[num.length - 1 - i];
13                 num[num.length - 1 - i] = cur;
14             }
15             return;
16         }
17         int pos = 0;
18         for(int i = point + 1; i < len; i ++){
19             if(num[i] > num[point]) pos = i;
20         }
21         int ttmp = num[point];
22         num[point] = num[pos];
23         num[pos] = ttmp; 
24         
25         for(int i = 1; i <= (len - point - 1) / 2; i ++){
26             int tmp = num[point + i];
27             num[point + i] = num[len - i];
28             num[len - i] = tmp;
29         }
30     }
31 }