My O(n) python code

  • 0

    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
                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):])
        nums[:] = sorted(nums)

  • 0

    @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.