Python Solution with explain

  • 0
    class Solution(object):
        def nextPermutation(self, nums):
            # find first position from right which num[pos] < num[pos+1]
            pos = None
            for i in xrange(len(nums)-2, -1, -1):
                if nums[i] < nums[i+1]:
                    pos = i
            if pos is None:
            # find the minimum number after pos, swap them, then reverse the slice after pos
            best = None
            for i in xrange(pos+1, len(nums)):
                if best is None:
                    best = i
                elif nums[i] > nums[pos] and nums[i] <= nums[best]:
                    best = i
            nums[pos], nums[best] = nums[best], nums[pos]
            nums[pos+1:] = nums[pos+1:][::-1]

Log in to reply

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