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,nums = nums,nums 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
AC Python solution with explanation
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.