Tags: "leetcode", "array", "greedy", access_time 1-min read

Edit this post on Github

Maximum Swap

Created: February 13, 2020 by [lek-tin]

Last updated: February 13, 2020

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1

Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2

Input: 9973
Output: 9973
Explanation: No swap.

Note

  1. The given number is in the range [0, 10^8]

Solution

class Solution:
    def maximumSwap(self, num: int) -> int:
        numChars = list(str(num))
        n = len(numChars)
        last = [0 for i in range(10)]

        for i in range(n):
            last[ord(numChars[i])-ord("0")] = i

        for i in range(n):
            # test the biggest number first
            j = 9
            # We wanna find out the largest digit on the right
            while j > int(ord(numChars[i])-ord("0")):
                if last[j] > i:
                    temp = numChars[i]
                    numChars[i] = numChars[last[j]]
                    numChars[last[j]] = temp
                    return int("".join(numChars))
                j -= 1

        return num