Next Permutation


  • 2

    Click here to see the full article post


  • 0
    C

    To find j, we can use a binary search between i and end.
    However this may not make it faster in real world, because for a random permutation, i won't be far away from end.
    If we know the array is almost sorted, then binary search will be better.


  • 1
    A

    If given a multitude of random testcases each with very long length, binary search of finding j will be faster.


  • 0
    A

    In the brute force approach shouldn't the space be O(n!) and not O(n)?
    Given n elements produce n! permutations and we need space to store n! permutations.


  • 0
    W

    For
    while (j >= 0 && nums[j] <= nums[i]), there is no need to test j >= 0, as there must be a number is bigger than nums[i].
    while (nums[j] <= nums[i]) is enough.


  • 0

    Your animation makes the illustration perfect! Thumbs up!


  • 0
    F

    Isn't the time complexity O(n! * n) for the brute force case? We have to compare all of the permutations to the original one/current closest (each comparision requres O(n) time)


  • 0
    V

    thx for the animation... helps a lot


  • 0
    V

    Isn't this incorrect? Should be nums[j] >= nums[i] since we are looking for a number that's greater than nums[i] where we found a break in the descending from left to right pattern. Can someone else double check this?

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

  • 0
    A

    while (j >= 0 && nums[j] <= nums[i]) {
    j--;
    }
    after this line ,before swap, i think an extra check for j>=0 is required. For Input [1,1] , j may become -1 according to this logic. So only swap when j >= 0 .


  • 0
    A

    Who can tell me which software can used to draw this type gif


  • 0
    U

    Great explanation!


  • 0
    N

    that is wise


  • 0
    W

    //this is my solution
    int lens = nums.length;
    int temp = 0;
    int start = 0;// 从第几个元素开始升序排列
    boolean isPossible = true;
    if (lens > 0) {
    for (int i = lens - 1; i >= 0; i--) {
    if (isPossible) {
    for (int j = lens - 1; j > i; j--) {
    if (nums[j] > nums[i]) {//find the position to reverse
    temp = nums[j];
    nums[j] = nums[i];
    nums[i] = temp;
    start = i;//Record this position
    isPossible = false;
    break;
    }
    }
    }

    		}
    
    	}
    
    	if (isPossible) {
    		for (int i = 0; i < (lens+1 )/ 2; i++) {//reverse nums
    			temp = nums[lens - i - 1];
    			nums[lens - i - 1] = nums[i];
    			nums[i] = temp;
    		}
    	} else {//reverse nums form start+1 to the end
    		for (int i = start + 1; i < (lens + start + 1) / 2; i++) {
    			temp = nums[i];
    			nums[i] = nums[lens + start - i];
    			nums[lens + start - i] = temp;
    		}
    	}

Log in to reply
 

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