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

这个题目光看例子一脸懵逼，谷歌翻译了一下：

实现下一个排列，它将数字重新排列成字典下一个更大的数字排列。
如果这种安排不可能，则必须将其重新排列为尽可能低的顺序（即按升序排序）。
更换必须就地，并且只使用恒定的额外内存。

还是看了半天，画了一下，大概明白意思，输入一个数组，所有数字可以排列组合，返回一个大一点的排列组合结果，比如123有123，132，213，231，312，321这6种排列组合

比如输入了123，那么比它稍大一点的就是132；假如传入321已经是最大的排列组合，就返回最小的一个123，大概意思就这样

从右往左遍历，找到右边比左边大的位置，因为既然要找稍大的，如果右边全部都比左边小，那就返回一个倒序的；否则，找到nums[i] > nums[i-1]，从i开始右边的找到最小值，和nums[i-1]换，再把i开始右边从小打到排序，基本就是稍大的排列组合了

下图的场景，这样考虑当然是满足的，但是写法还是错误的，比如[4,1,2,6,7,5,3]，7>6，然后7，5，3最小值为3，将6和3换了之后，这个排列组合更小了，根本就不满足要求，所以问题在一开始寻找就有问题，头大，先列一下错误方法

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));
    }
}

修身养性了几天，再继续看下这道题

其实仔细想想，首先找到了第一个a[i]<a[i+1]的位置，而右边是从大到小的，因此只需要找一个a[j] > a[i]，将他们两个交换，就能保证前半部分变大了，而从a[i+1]开始，只需要从小到大就行了，这样我们在找这个a[j]的时候，可以从右往左找大于a[i]的第一个，那么必然也是右边部分最小的一个满足要求的，交换之后，后半部分翻转位置即可

总得来看，下图

（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，翻转成升序返回

具体Java源码

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;
        }
    }
}

可读性还是不太好