[Leetcode] Next Permutation

 1 /*
 2 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. 
 3 
 4 If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). 
 5 
 6 The replacement must be in-place, do not allocate extra memory. 
 7 
 8 Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
 9 1,2,3 → 1,3,2
10 3,2,1 → 1,2,3
11 1,1,5 → 1,5,1
12 
13 */
14 
15 public class Solution {
16     public void nextPermutation(int[] nums) {
17         //search for the first decrease order,from right to left-hand
18         int i=nums.length-1;
19         for(;i>0;i--){
20             if(nums[i]>nums[i-1]){
21                 break;
22             }
23         }
24         //if there is no decrease order, just return the increase order
25         if(i==0){
26             Arrays.sort(nums);
27             return;
28         }
29         i--;
30         int j=nums.length-1;
31         for(;j>=0;j--){
32             if(nums[j]>nums[i]){//get it here
33                 int tmp = nums[j];
34                 nums[j]=nums[i];
35                 nums[i]=tmp;
36                 break;
37             }
38         }
39         //swap
40         int begin=i+1;
41         int end=nums.length-1;
42         while(begin<end){//should focuse on how to swap, the two elements
43             int tmp = nums[begin];
44             nums[begin]=nums[end];
45             nums[end]=tmp;
46             begin++;
47             end--;
48         }
49     }
50 }