Python 72ms solution


  • 0

    #For explanation, you can refer:
    http://www.nayuki.io/page/next-lexicographical-permutation-algorithm

    class Solution(object):
        def getPivot(self, nums):
            index = len(nums) - 1
            prev  = nums[index]
            index -= 1
            while index >= 0:
                if nums[index] < prev:
                    return index
                prev = nums[index]
                index -= 1
            return -1
        
        def nextPermutation(self, nums):
            length = len(nums)
            pivot = self.getPivot(nums)
            if pivot == -1:
                nums.sort()
                return
            
            pivotValue = nums[pivot]
            replacedIndex = -1
            for i in reversed(range(pivot+1, length)):
                if nums[i] > pivotValue:
                    replacedIndex = i
                    break
            
            tmp = nums[replacedIndex]
            nums[replacedIndex] = nums[pivot]
            nums[pivot]   = tmp
            
            i = 0
            while i < (length - pivot - 1) / 2:
                tmp = nums[pivot+1+i]
                nums[pivot+1+i] = nums[length-1-i]
                nums[length-1-i] = tmp
                i += 1

Log in to reply
 

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