LeetCode-array-NextPermutation

题目：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

题目大意，给到一串数组，求下一排列顺序，例如3,2,1 → 1,2,3，321已结是最大的了，所以下一排列就是123最小的，例如 [1,2,3]数组，的下一排列是[1,3,2]可以看出来，好像从数组的后面判断，如果前一位小于后一位将调换位置，再看数组是[1,2,4,3]那么下一排列正确答案是[1,3,2,4]，可以分析出从后往前判断，2小于4那么不能将2，4对换，换后并不是下一排列，而是下下下..排列了，应该将2,4的下标记录后，从2的后面判断最小大于2的数字是3，那么2,3对换成为[1,3,4,2]，这时还得将后面的4，2重新小到大排列后得到最后结果
[1,3,2,4]，OK。

java代码如下

package LeetCode1;

import java.util.Arrays;

/**
 * Created by Wangjianxin on 2017/7/11 0011.
 */

public class NextPermutation {

    public static void main(String[] args) {
        int[] s = {2,3,1};
        nextPermutation(s);
    }

    public static void nextPermutation(int[] nums) {

        int len = nums.length;
        int leftindex = -1;
        int left = len - 2;
        int right = len - 1;
        //先从后往前找出i比i+1小的数字的下标
        for(int i = len - 2; i >=0;--i){
            System.out.println(nums[right]);
            if (nums[left] < nums[right]){
                leftindex = left;
                break;
            }
            left -- ;
            right --;
        }
        System.out.println(leftindex);
        if(leftindex != -1){
            //找到后，从这个数之后找到最小大于这个数的元素
            int k = Integer.MAX_VALUE;
            int kindex = 0;
            for(int i = leftindex+1; i < len;i++){
                int min = nums[i] - nums[leftindex];
                if(k > min && min > 0){
                    k = min;
                    kindex = i;
                }
            }
            int temp = 0;
            temp =  nums[kindex];
            nums[kindex] = nums[leftindex];
            nums[leftindex] = temp;

            System.out.println(Arrays.toString(nums));
            sort(nums,leftindex + 1,len-1);
        }else{
         Arrays.sort(nums);
        }

        System.out.println(Arrays.toString(nums));
    }
    //这里的参数end没有用到
    public static int[] sort(int[] s, int begin,int end){
        for(int i= begin ;i <s.length;i++){
            for(int j = begin ;j  < s.length -1; j++){
                if(s[j] > s[j+1]){
                    int temp = s[j];
                    s[j] = s[j+1];
                    s[j+1] = temp;
                }
            }
        }
        return s;
    }

}