Given a list of integers, which denote a permutation.

Find the next permutation in ascending order.

Notice

The list may contains duplicate integers.

Have you met this question in a real interview?

Yes

Example

For[1,3,2,3], the next permutation is[1,3,3,2]

For[4,3,2,1], the next permutation is[1,2,3,4]

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: An array of integers that's next permuation
     */
    public int[] nextPermutation(int[] nums) {
        // write your code here
        //1324
        //1342
        //17986
        //18678
        //1234
        //1332
        //2133
        //1333
        //3133

        //12345
        //1332
        //3113
        //121

        //121
        //1121
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        //i = 2
        int i = nums.length - 1;
        for (i = nums.length - 1; i > 0; i--) {
            if (nums[i] <= nums[i - 1]) {
                continue;
            }
            break;
        }

        //i = 1
        if (i > 0 && i == nums.length - 1) {
            swap(i, i - 1, nums);
            return nums;
        }

        int j = i + 1;//j = 2
        for (j = i + 1; i > 0 && j < nums.length; j++) {
            if (nums[j] <= nums[i - 1] || j == nums.length - 1) {
                break;
            }
        }

        //j = 2, i = 1

        if (i > 0 && nums[j] <= nums[i - 1]) {
            j = j - 1;
        }

        //j = 1 i = 1

        if (i > 0) {
            swap(i - 1, j, nums);
        }

        reverse(i, nums.length - 1, nums);

        return nums;

    }

    public void swap(int a, int b, int[] nums) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c; 
    }

    public void reverse(int a, int b, int[] nums) {
        int start = a;
        int end = nums.length - 1;

        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }



}

1. self. need to think what's the next number of the same digit that's greater than current number but less than all other numbers that's greater than the current number. so find the first backward desc digit i and find the smallest digit that's greater than digit i within (i + 1, nums.length - 1). and if there are duplicates number that's greater than digit i, we need to find the last digit of that value and swap

public class Solution {
    /*
     * @param nums: A list of integers
     * @return: A list of integers
     */
    public int[] nextPermutation(int[] nums) {
        // write your code here
        //1,2,3,4,5
        //1,2,3,5,4
        //1,2,4,3,5
        //1,2,4,5,3
        //1,2,5,3,4
        //1,2,5,4,3
        if (nums == null || nums.length == 0) {
            return nums;
        }
        int i = nums.length - 1;
        //stop at first asc order from back to front
        for (i = nums.length - 1; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
                break;
            }
        }

        if (i == 0) {
            reverse(0, nums);
            return nums;
        }

        //need to get the index of the min number that's greater than nums[i - 1]
        int min = nums[i];
        int minIndex = i;
        for (int j = i; j < nums.length; j++) {
            if (nums[j] > nums[i - 1] && nums[j] <= min) {
                min = nums[j];
                minIndex = j;
            }
        }

        swap(i - 1, minIndex, nums);
        reverse(i, nums);
        return nums;
    }

    public void swap(int a, int b, int[] nums) {
        int aNew = nums[a];
        nums[a] = nums[b];
        nums[b] = aNew;
    }

    public void reverse(int start, int[] nums) {
        int end = nums.length - 1;
        while (start < end) {
            swap(start, end, nums);
            start++;
            end--;
        }
    }
}