Python easy to understand O(nlogn) time


  • 0
    L

    Two steps:

    1. Compare s with sorted string t to find the two numbers we need to swap.
    2. Swap them: search from the beginning to find the smaller number to swap; them search from the end to find the larger number to swap.
    class Solution(object):
        def maximumSwap(self, num):
            """
            :type num: int
            :rtype: int
            """
            t = sorted(str(num), reverse = True)
            s = list(str(num))
            n = len(t)
            swap1 = swap2 = ''
            for i in range(n):
                if t[i] != s[i]:
                    swap1 = s[i]
                    swap2 = t[i]
                    break
            index = 0
            for i in range(len(s)):
                if s[i] == swap1:
                    s[i] = swap2
                    index = i
                    break
            for i in range(len(s)-1, index, -1):
                if s[i] == swap2:
                    s[i] = swap1
                    break
            return int(''.join(s)) if swap1 != '' and swap2 != '' else num
    

Log in to reply
 

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