### LeetCode 31：Next Permutation

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 and use only constant 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`

```实现下一个排列，它将数字重新排列成字典下一个更大的数字排列。

Java源码，修修补补了半天，当然还是错的

`package com.lihuia.leetcode;import java.util.Arrays;/** * Copyright (C), lihuia.com * FileName: Solution * Author:   lihui * Date:     2018/10/8 */public class Solution {    public void nextPermutation(int[] nums) {        /**         *  4 1 6 2 7 5 3         *  4 1 6 3 7 5 2         *  4 1 6 3 2 5 7         */        int len = nums.length;        if (nums != null && len != 1) {            int i = 0;            //找出交换数字的位置            for (i = len - 1; i > 0; i--) {                if (nums[i] > nums[i - 1]) {                    break;                }            }            if (i != 0) {                int j = 0;                int minIndex = i;                //找出右方最小值                for (j = i; j < len; j++) {                    if (nums[j] < nums[minIndex]) {                        minIndex = j;                    }                }                //交换位置                int temp = nums[minIndex];                nums[minIndex] = nums[i - 1];                nums[i - 1] = temp;                //右方数字(i, len - 1)从小到大排序                for (int m = i; m < len; m++) {                    for (int n = m + 1; n < len; n++) {                        if (nums[m] > nums[n]) {                            int tmp = nums[m];                            nums[m] = nums[n];                            nums[n] = tmp;                        }                    }                }            }        }        System.out.println(Arrays.toString(nums));    }}`

（1）从右往左，找到a[i]<a[i+1]，此时i=3

（2）从右往左，找到a[j] > a[i]，此时i=3，j=4

（3）a[i]和a[j]交换

（4）a[i+1]到a[len-1]翻转颠倒位置

（5）如果一开始就是降序排列，第（1）步，i=-1，翻转成升序返回

`package com.lihuia.leetcode;/** * Copyright (C), lihuia.com * FileName: Solution * Author:   lihui * Date:     2018/10/8 */public class Solution {    public void nextPermutation(int[] nums) {        /**         *  4 1 6 2 7 5 3         *  4 1 6 3 7 5 2         *  4 1 6 3 2 5 7         */        int len = nums.length;        if (len == 1) {            return;        }        int i = 0;        //从右往左，找到第一个左边<右边的位置        for (i = len - 2; i >= 0; i--) {            if (nums[i + 1] > nums[i]) {                break;            }        }        //整个数组从大到小排列，直接翻转返回        if (i == -1) {            for (int left = 0, right = len - 1; left < right; left++, right--) {                int tmp = nums[left];                nums[left] = nums[right];                nums[right] = tmp;            }            return;        }                int j = 0;        for (j = len - 1; j >= i + 1; j--) {            if (nums[j] > nums[i]) {                break;            }        }        int temp = nums[i];        nums[i] = nums[j];        nums[j] = temp;        for (int left = i + 1, right = len - 1; left < right; left++, right--) {            int tmp = nums[left];            nums[left] = nums[right];            nums[right] = tmp;        }    }}`