2 ms simple Java solution


  • 0
    H
    public void nextPermutation(int[] nums) {
        int N = nums.length, temp;
        if (N == 0) return;
        int i = N-2;
        for (; i>=0; i--) {
            if (nums[i] < nums[i+1]) {
                break;
            }
        }
        int j = N-1;
        while (i != -1 && i < j-1 && nums[j] <= nums[i]) j--;
        if (i != -1) {
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        for (i = i+1, j = N-1; i < j; i++,j--) {
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    

    For example: Input 1 2 5 9 8 7 4

    1. We find the first element position posI which is less than the element behind. (posI=2)
    2. Then find the first element position posJ which is higher than the posI element. (posJ=5)
    3. Swap the element posI, posJ
    4. We can get input 1 2 7 9 8 5 4
    5. We continue swapping elements (9,8,5,4) until we got results: (1,2,7,4,5,8,9)

    But we have to deal with some details.
    For example 1 2 4 4 4, so step 2 is higher than or equal the posI element.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.