Next Permutation

 This question is not hard. Firstly, we look for the first number larger(num[breakIdx]) than its previous one, starting from end of array. Once this number is found, what we need to do is to swap it with next greater number, e.g. num[swapIdx], of num[breakIdx] among numbers we have visited. After this operation, reverse the order of numbers between num[breakIdx] and end of array.

First 2 steps above make sure that result number is larger than before. And since the numbers we have visited are in the decreasing order, thus they form the largest possible number. Thus reverse the order, we can get a increasing order number, which should be the smallest  possible number.


public class Solution {
    public void nextPermutation(int[] num) {
        if(num.length <= 1) return;
        int breakIdx = -1, swapIdx = -1;
        for(int i = num.length - 1; i >= 1 ; i --){
            if(num[i] > num[i-1]){
                breakIdx = i - 1;
                break;
            }
        }
        if(breakIdx != -1){// find the next greater number of num[breakIdx], then swap with num[breakIdx]
            for(int i = breakIdx+1; i <= num.length - 1; i ++){
                if(num[i] <= num[breakIdx]){
                    swapIdx = i - 1;break;
                }
            }
            if(swapIdx == -1){// i in above loop hits the end of num,
                              // i.e. num[breakIdx] is smaller than anyone of rest elements
               
                int tmp = num[breakIdx];
               
                num[breakIdx] = num[num.length - 1];
                num[num.length - 1] = tmp;
               
            }
            else{// swap this number with num[breakIdx]
                int tmp = num[breakIdx];
               
                num[breakIdx] = num[swapIdx];
                num[swapIdx] = tmp;
            }
            breakIdx = breakIdx + 1;
            reverse(num,breakIdx, num.length - 1);
           
        }
        else{
            //reverse the order of the whole num array
            reverse(num,0, num.length - 1);
           
        }
    }
   
   
    public void reverse(int[] num, int left, int right){
        if(left == right) return;
       
        int mid = (left + right)/2;
        int i = left;
        int j = right;
        for(; i <= mid && i < j; ){
            int tmp = num[i];
            num[i] = num[j];
            num[j] = tmp;
            i++;
            j--;
        }
    }
}