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;
    		}
    	}

  • 0
    Q

    Cheeky answer using the STL:

        void nextPermutation(vector<int>& nums) {
            std::next_permutation(nums.begin(), nums.end());
        }
    

    :)


  • 0
    X

    very very good solution!you are so smart!


  • 0
    G

    wow, so smart!!!!!


  • 0
    S

    The while loop condition on 'j' can be changed to "j >= i+1" since we do not need to traverse all the way back to j>=0 as we need to find the first larger element to the right of "i-1". Moreover, nums[i] > nums[i-1] due to the previous for loop and when the while loop breaks, the correctness is not affected.


Log in to reply
 

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