Next Permutation

 1 public class Solution {
 2     public void nextPermutation(int[] num) {
 3         // Note: The Solution object is instantiated only once and is reused by each test case.
 4         int length = num.length;
 5         int index = - 1;
 6         for(int i = length - 1; i >= 1; i--){
 7             if(num[i] > num[i - 1]){
 8                 index = i;
 9                 break;
10             }
11         }
12         
13         if(index == -1){
14             reverseArray(num, 0, length - 1);
15         } else {
16             int biggerIndex = findBig(num[index - 1], index, num);
17             swap(num, biggerIndex, index - 1);
18             reverseArray(num, index, length - 1);
19         }
20     }
21     
22     public int findBig(int sentinal, int index, int[] num){
23         int bigIndex = index;
24         int bigValue = num[index];
25         for(int i = index + 1; i < num.length; i++){
26             if(num[i] > num[index - 1] && num[i] <= bigValue){
27                 bigValue = num[i];
28                 bigIndex = i;
29             }
30         }
31         return bigIndex;
32     }
33     
34     public void reverseArray(int[] num, int start, int end){
35         while(start < end){
36             swap(num, start, end);
37             start ++;
38             end --;
39         }
40     }
41     
42     public void swap(int[] num, int start, int end){
43         int tmp = num[start];
44         num[start] = num[end];
45         num[end] = tmp;
46     }
47 }