Python solution with comments.


  • 0
    C
    def nextPermutation(self, nums):
        i = l = len(nums)-1
        while i > 0:
            # find the right most pair where nums[i] > nums[i-1]
            if nums[i] > nums[i-1]:
                tmp = 0
                for j in xrange(l, i-1, -1):
                    if nums[j] > nums[i-1]:
                        tmp = j
                        break
                # exchange nums[i-1] and the right most element which larger than nums[i-1] 
                nums[i-1], nums[tmp] = nums[tmp], nums[i-1]
                # reverse from i to the end
                for j in xrange(i, 1+i+(l-i)/2):
                    nums[j], nums[l+i-j] = nums[l+i-j], nums[j]
                break
            i -= 1
        # if nums are in descending order
        if i == 0:
            nums.reverse()

  • 0
    C

    Here is a revised version which look much better:

    def nextPermutation(self, nums):
        i = j = len(nums)-1
        while i > 0 and nums[i] <= nums[i-1]:
            i -= 1
        if i > 0:
            while nums[j] <= nums[i-1]:
                j -= 1
            nums[i-1], nums[j] = nums[j], nums[i-1]
        nums[i:] = reversed(nums[i:])

  • 0

    Creating nums[i:] violates the "do not allocate extra memory" requirement, though.


  • 0
    C

    Yes, indeed, it's just for convenience. Based on the requirement we can reverse in place:
    for j in xrange(i, 1+i+(l-i)/2):
    nums[j], nums[l+i-j] = nums[l+i-j], nums[j]


  • 0

    Yeah, I've seen it in your original code. I think I'd prefer this, though:

        while i < l:
            nums[i], nums[l] = nums[l], nums[i]
            i += 1
            l -= 1
    

    It's more lines, but much simpler.


  • 0

    Or like this, also very simple:

        for j in xrange((l+1-i)/2):
            nums[i+j], nums[~j] = nums[~j], nums[i+j]
    

  • 0
    C

    Your answer always looks like magic, very nice!


Log in to reply
 

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