Short O(n) Python AC Code


  • 0
    H

    Solution

    1. Find the first increasing digits in the number which separate the number into two parts.
    2. Find the maximum digit in the second part.
    3. Find the first digit in the first part which is smaller than the maximum digit in step 2 and swap them.
    class Solution:
        def maximumSwap(self, num):
            """
            :type num: int
            :rtype: int
            """
            nums = [i for i in str(num)]
            increasing = [i for i, v in enumerate(nums) if i > 0 and nums[i-1] < v]
            if not increasing:
                return num
            max_digit = max(nums[increasing[0]:])
            max_index = [i for i, v in enumerate(nums) if v == max_digit][-1]
            for i in range(max_index):
                if nums[i] < nums[max_index]:
                    nums[i], nums[max_index] = nums[max_index], nums[i]
                    break
            return int("".join(nums))
            
    

Log in to reply
 

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