My O(n) python code


  • 0
    W

    class Solution(object):
    def nextPermutation(self, nums):
    """
    :type nums: List[int]
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    # start from the tail, back to the head.
    # if next number is not smaller than the max of the encountered nums (aka the previous number):
    # go on to the next number
    # else:
    # swap this "next number" with the next bigger num in the encountered num
    # sort the encountered sublist

        n = len(nums)
        i = n - 2
        while i >= 0:
            if nums[i] >= nums[i + 1]:
                i -= 1
            else:
                for j in range(n-1, i, -1):
                    if nums[j] > nums[i]:
                        tmp = nums[j]
                        nums[j] = nums[i]
                        nums[i] = tmp
                        nums[(i+1):] = sorted(nums[(i+1):])
                        return
        nums[:] = sorted(nums)
        return

  • 0
    X

    @wwwwwhatever In worst case your sorted() will give you O(nlogn), I think. So this is a O(nlogn) program, I guess.


Log in to reply
 

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