Beat 84% Python code. With idea description


  • 0
    X

    Main idea: loop through the list backwards and find the first element such that nums[i - 1] < nums[i]. We call i - 1 the pivot point. We find the minimum element in nums[pivotPoint:] such that it is bigger than nums[pivotPoint]. We call this pivotPoint2. We swap pivotPoint and pivotPoint2, then we sort the nums[pivotPoint:] in place.

    Example:
    5, 7, 9, 4, 1
    loop backwards: 1,4,9,7. Stop, since 9 > 7. Now 7 is pivot point. In [9,4,1], 9 is the minimum number which is biggeer than 7. we swap 9 and 7: 5,9,7,4,1. Then we sort [7,4,1] in place, we got [1,4,7], nums becomes [5,9,1,4,7].

    Finished

    O(n + nlogn) = O(nlogn), apprently.

    class Solution(object):
        def nextPermutation(self, nums):
            L = len(nums)
            pivotPoint = -1
            for i in range(L - 1, 0, -1):
                if nums[i - 1] < nums[i]:
                    pivotPoint = i - 1
                    break
            if pivotPoint == -1:
                nums.sort() #O(nlogn)
                return
            minn = max(nums) # O(n)
            pivotPoint2 = -1
            for i in range(pivotPoint, L):
                if nums[i] > nums[pivotPoint] and nums[i] <= minn:
                    minn = nums[i]
                    pivotPoint2 = i
            buff = nums[pivotPoint2]
            nums[pivotPoint2] = nums[pivotPoint]
            nums[pivotPoint] = buff
            nums[pivotPoint + 1:] = sorted(nums[pivotPoint + 1:]) # in place
            return
    
    

Log in to reply
 

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