Next Permutation

Q:
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
A:
思路就是：从右向左，找到最后一个升序排列的数。 例如1 , 2, 5, 7, 6,4 这里， 的7就是最后一个升序排列的数。 取出它 的index ，标记为：rightIndex。
再从右向左，找出比第一个  rightIndex-1这个位置的数大的数字。  这里，比 5大的第一个数字是 6，  记录下来。
首先交换5,6的位置。  然后，现在已经是bigger了，  而从7开始，从左向右是i降序排列， 我们把它你转过来即可。

如果刚开始的时候，找到rightIndex == 0.那么已经是最大的了。 即： 7,6,5,4,2,1d的排列。我们只需要逆转即可。

public class Solution {
    public void nextPermutation(int[] nums) {
        int n  = nums.length, k = n-2;
        while(k >=0 && nums[k] >= nums[k+1] )//find first index smaller than its next
            k--;
        
        if(k>=0){
            int i = n-1;// search from back for the first 
            while(nums[i] <= nums[k] )
                i--;
            //swap nums[i] with nums[k]
            int tmp = nums[i];
            nums[i] = nums[k];
            nums[k] = tmp;
        }
        Arrays.sort(nums,k+1,n);
    }
}

************  第一遍****************

public class NextPermutation {
    public void nextPermutation(int[] num) {
        // coz no extra space is allowed, we use trick method to swap num
        if (num == null || num.length == 0 || num.length == 1) {
            return;
        }
        int rightIndex = num.length -1; // the right most index after which, num in descending order
        while(rightIndex -1 >=0 ){
            if(num[rightIndex-1]>= num[rightIndex] ){
                rightIndex --;
            }else{
                break;
            }
        }
        if(rightIndex > 0 ){
            // find first that are bigger than num[rightIndex-1]
            int firstBigger;
            for(firstBigger =num.length-1;firstBigger>=rightIndex;firstBigger--){
                if(num[firstBigger]> num[rightIndex-1]){
                    break;
                }
            }
            swapArray(num,rightIndex-1,firstBigger); // swap the first&lowest one that is bigger 
            // reverse the rest of the list
            int i =rightIndex, j = num.length-1;
            while(i<j){
                swapArray(num,i,j);
                i++;
                j--;
            }
            
        }else{  // rightIndex == 0  ,  return the lowest  possible order, i.e. reverse the num
            int i =0, j = num.length-1;
            while(i<j){
                swapArray(num,i,j);
                i++;
                j--;
            }
        }
    }

    private void swapArray(int[] num, int i, int j) {
        // swap the array in-place
        int tmp = num[i];
        num[i] = num[j];
        num[j]= tmp;
    }
}

Mistakes:
1:刚开始思路错误。 去找前两个  left <  right 的去了。

Learned:
----------------------------2nd ------------------------  same idea.  codes is simplified------------

public class Solution {
    public void nextPermutation(int[] num) {
        if(num.length<=1)
            return;
        //backward, to find first non increasing index
        int i=num.length-2;
        while(i>=0 && num[i]>=num[i+1])
            i--;
        
        if(i>=0){ // find first after i , that is bigger than i
            int j = num.length-1;
            while(num[j]<=num[i])
                j--;
            swap(num,i,j);
        }
        i++; // point i to the next position
        int j = num.length-1;
        while(i<j){
            swap(num,i,j);
            i++;
            j--;
        }
    }
    private void swap(int[] num, int i ,int j){
            num[i] += num[j];
            num[j] = num[i] - num[j];
            num[i] = num[i] - num[j];
    }
}

********************以前做过的，都TMD忘光了。╮(╯▽╰)╭********************