Python solution with comments


  • 0
    S
    class Solution(object):
        def nextPermutation(self, nums):
            n = len(nums)
            if n <= 1: return
    
            # bring the smallest number (greater than the threshold) to the front in the range [start, end] inclusive
            def bring_min_to_front(nums, start, end, threshold):
                min_index = end
                min_value = float('Inf')
                found = False
                for j in range(end, start - 1, -1):
                    if threshold < nums[j] < min_value:
                        found = True
                        min_value = nums[j]
                        min_index = j
    
                if found:
                    nums[start], nums[min_index] = nums[min_index], nums[start]
    
            for i in range(n - 1, 0, -1):
                if nums[i - 1] < nums[i]:
                    """
                     1  7 5 2 1
                    i-1 i
    
                     1  2 5 7 1 (bring smallest (2) from [i, n) and > threshold (1) to position i)
                    i-1 i
    
                     2  1 5 7 1 (swap [i-1] and [i])
                    i-1 i
    
                     2  1 1 7 5 (adjust the remaining array from [i, n))
                    i-1 i
    
                     2  1 1 5 7
                    i-1 i
                    """
                    bring_min_to_front(nums, i, n - 1, nums[i - 1])
                    nums[i - 1], nums[i] = nums[i], nums[i - 1]
                    for j in range(i, n): bring_min_to_front(nums, j, n - 1, float('-Inf'))
                    return
    
            # reverse array if all numbers are in descending order
            for i in range(int(n / 2)):
                nums[i], nums[n - 1 - i] = nums[n - 1 - i], nums[i]

Log in to reply
 

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