python O(n) O(1) solution


  • 0
    Z

    The first thing came into mind is find the maximum number and swap it with the first element.

    then you have the case where the digits are partially sorted. like 997324567
    my idea is to divide the digits into two parts, descending part and the non-descending part. like 99732 and 4567 in the above case
    my greedy strategy is find the maximum number in the second part and swap it into the first part whenever it can

    non proof given and code it no optimal.

    surely there are some ways to arrange it more elegantly and in less lines.

    class Solution(object):
        def maximumSwap(self, num):
            """
            :type num: int
            :rtype: int
            """
            nums = list(str(num))
            n = len(nums)
            bi = n - 1
            pref = 0x7fffffff
            for i in range(n):
                x = ord(nums[i])
                if x <= pref:
                    pref = x
                else:
                    bi = i
                    break
            
            maxj = bi 
            for j in range(bi, n):
                if ord(nums[j]) >= ord(nums[maxj]):
                    maxj = j
                    
            for i in range(0, bi):
                if ord(nums[i]) < ord(nums[maxj]):
                    nums[i], nums[maxj] = nums[maxj], nums[i]
                    break
                    
            return int("".join(nums))
    
    """
    2736
    9973
    99273
    2376
    2367
    999838881438
    12
    2345678
    22334455667788
    87654321
    88776655443322
    """
            
    

Log in to reply
 

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