Paste_Image.png

My code:

import java.util.Arrays;

public class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1)
            return;
        int i = nums.length - 2;
        for (; i >= 0; i--) {
            if (nums[i] >= nums[i + 1])
                continue;
            else {
                int diff = Integer.MAX_VALUE;
                int minDiffIndex = 0;
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[j] - nums[i] > 0 && nums[j] - nums[i] < diff) {
                        diff = nums[j] - nums[i];
                        minDiffIndex = j;
                    }
                }
                int temp = nums[minDiffIndex];
                nums[minDiffIndex] = nums[i];
                nums[i] = temp;
                Arrays.sort(nums, i + 1, nums.length);
                break;
            }
        }
        if (i < 0)
            reverse(nums);
    }
    
    private void reverse(int[] nums) {
        int[] temp = new int[nums.length];
        for (int i = 0; i < nums.length; i++)
            temp[i] = nums[nums.length - 1 - i];
        nums = temp;
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] a = {3, 2, 1};
        test.nextPermutation(a);
        
    }
}

My test result:

这次作业有点难。昨天写好了，因为简书的渣网页，登陆不进去，所以只能现在给发上来。

其实这类题， 往往可以举一个复杂点的例子，然后思考下自己的脑子是怎么思考的。
很明显，就是从末尾向头部遍历，如果一直是递增的就不管他，然后如果突然变小，就要把这个小的和之前右侧中，与该值最接近且比他大的值交换，然后将右侧数列重新排序。
最后考虑下如果直接是逆序排列的，只要将它反转即可。推荐一个博客。
http://bangbingsyb.blogspot.com/2014/11/leetcode-next-permutation.html
讲的比我清楚。

**
总结：Array, 在草稿纸上多画画例子，就会有思路了。
**

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1)
            return;
        int change = -1;
        /** find the index which should be changed at first */
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                change = i;
                break;
            }
        }
        /** if the whole array is arranged reversely, reverse the whole array */
        if (change == -1) {
            for (int i = 0; i < nums.length / 2; i++) {
                int temp = nums[i];
                nums[i] = nums[nums.length - 1 - i];
                nums[nums.length - 1 - i] = temp;
            }
            return;
        }
        /** find the elem which is minimum but bigger than nums[change] */
        int min = Integer.MAX_VALUE;
        int minIndex = change + 1;
        for (int i = nums.length - 1; i > change; i--) {
            if (nums[i] < min && nums[i] > nums[change]) {
                min = nums[i];
                minIndex = i;
            }
        }
        /** swap nums[change] and nums[minIndex] */
        int temp = nums[change];
        nums[change] = nums[minIndex];
        nums[minIndex] = temp;
        /** sort the rest array */
        Arrays.sort(nums, change + 1, nums.length);
    }
}

这次一遍就做出来了。。。进步了很多。主要也是有点印象。
刚投了份实习申请，一个小时后就被拒了。。。

Anyway, Good luck, Richardo!