31. Next Permutation (Medium)

https://leetcode.com/problems/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,31,3,2
3,2,11,2,3
1,1,51,5,1

Solutions

class Solution {

    // This problem is complex, leave it.

    // 1. Look for consecutive pair that in ascending order from tail.
    // 2. Sort out the proper element swapping with the head of above ascending pair.
    // 3. Swap elements and then reverse

    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        // Search for consecutive pair in ascending order
        int i = nums.length - 1;
        while (i > 0 && nums[i] <= nums[i - 1]) {
            i--;
        }

        if (i == 0) {
            reverse(nums, 0, nums.length - 1);

            return;
        }

        // To reach here, nums[i] > nums[i-1], i != 0, which means array[i:len-1]
        // are in descending order

        // [1,2,3,2,4,3,2,1], nums[i-1]=2, nums[i]=4,nums[j]=3

        // Scan for element > nums[i-1], apparently, j >= i since nums[i] > nums[i-1]
        // It will stop at j=i if elements after i are all no greater than nums[i-1]
        int j = nums.length - 1;
        while (nums[j] <= nums[i - 1]) {
            j--;
        }

        // [1,2,3,2,4,3,2,1]->[1,2,3,3,4,2,2,1]
        swap(nums, i - 1, j);

        // We can say for sure that elements after i-1 are still in descending order after swapping.
        // For instance, the original array is [1,2,3,a,b,c,d,e,f], subject to a < b, b>=c>=d>=e>=f, d>a>e
        // so the nums[i-1]=a, nums[i]=b, nums[j]=d. After swapping, [1,2,3,d,b,c,a,e,f].
        //
        // To prove our assumption, b,c,a,e,f must be subject to b>=c>=a>=e>=f. 1. since c>=d and d>a, we get c>a;
        // since a<=d, and a>e, e<d. To sum up, the hypothesis is proved right.

        // Never the less, to make it easy, we can also use Arrays.sort(nums, i, len);

        // [1,2,3,3,4,2,2,1]->[1,2,3,3,1,2,2,4]
        reverse(nums, i, nums.length - 1);
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    public void swap(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
}

Incorrect Solutions

class Solution {

    // TODO Incorrect solution

    // The intuition of solving this problem is scanning the array from tail,
    // swap a certain pair that in ascending order. Then, sort values after
    // the swapping slot by ascending order.

    // [1,2]->2,1
    // [2,3,1]->3,1,2
    // [1,3,2]->[2,1,3]
    // [1,2,3,6,5,4]->[1,2,4,3,5,6]

    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        // [4,2,0,2,3,2,0], the first sorted out pair is (0,2), but (2,3) is more proper
        // so we need to list all the possible ascending pairs and the pair of maximum starting index
        // is the desired one.

        int len = nums.length;
        for (int i = len - 1; i >= 1; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i]) {
                    swap(nums, i, j);

                    Arrays.sort(nums, j + 1, len);

                    return;
                }
            }
        }

        // If the given array is in descending order, take turns in swapping elements
        // from head to tail and make the array in ascending order.

        int left = 0;
        int right = len - 1;

        while (left < right) {
            swap(nums, left, right);

            left++;
            right--;
        }
    }

    public void swap(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
}

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-02-28 13:22:28

results matching ""

    No results matching ""