AC Python solution with explanation


  • 0
    S
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        #This is a math problem. From right to left, find the first one decreasing from the right. Num1
        #Then start from the right again, to find the first one larger than Num1
        #Swap Num1 and Num2, and then reverse all the following arrays after position of Num1
        #Time complexity, O(n), two scan
        #Spcae complexity, O(1), in place
        if len(nums) < 2:
            return
        if len(nums) == 2:
            nums[0],nums[1] = nums[1],nums[0]
            return
        start = len(nums)-2
        while start >= 0:
            if nums[start] < nums[start+1]:
                break
            start -= 1
        if start < 0:
            nums.reverse()
            return
        for end in xrange(len(nums)-1,start,-1):
            if nums[end] > nums[start]:
                break
        nums[start], nums[end] = nums[end],nums[start]
        nums[start+1:] = nums[:start:-1] #Note this method to reverse in place!!
        return

  • 0
    F

    I like

    nums[start+1:] = nums[:start:-1]

    but is better than build in reverse() ?


Log in to reply
 

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