forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
maximum-swap.py
33 lines (31 loc) · 969 Bytes
/
maximum-swap.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Time: O(logn), logn is the length of the number string
# Space: O(logn)
# 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:
# The given number is in the range [0, 10^8]
class Solution(object):
def maximumSwap(self, num):
"""
:type num: int
:rtype: int
"""
digits = list(str(num))
left, right = 0, 0
max_idx = len(digits)-1
for i in reversed(xrange(len(digits))):
if digits[i] > digits[max_idx]:
max_idx = i
elif digits[max_idx] > digits[i]:
left, right = i, max_idx
digits[left], digits[right] = digits[right], digits[left]
return int("".join(digits))