10 lines Python solution - 59ms


  • 0
    H

    """
    Step1: Travese backward find the first appreance of nums[i-1] < nums[i]
    Step2: Sort nums[i:] in ascending order
    Step3: Find nums[j] in nums[i:n] that is just larger than nums[i-1], and switch nums[j] with nums[i-1]
    Note: if nums in the original list is already in descending order, return the next permutation as nums sorted in ascending order
    """
    class Solution(object):
    def nextPermutation(self, nums):
    for i in range(len(nums)-1,0,-1):
    if nums[i] > nums[i-1]:
    nums[i:] = sorted(nums[i:])
    j = i
    while nums[j] <= nums[i-1]:
    j += 1
    nums[i-1],nums[j] = nums[j],nums[i-1]
    break
    elif i==1:
    nums.reverse()


Log in to reply
 

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