题目描述：

LeetCode 670. Maximum Swap

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⁸]

题目大意：

给定非负整数，至多对调其中的两个数字，使数字最大化

解题思路：

记输入整数为num，其每位数字的数组为nums，倒序排列后的数组为numt

从左向右（高位到低位）遍历nums, numt，记当前数字分别为m, n, 下标为i

    若m != n：则将nums[i + 1 .. size]的最后一个最大值maxv与m对调

将nums恢复为数字并返回

Python代码：

class Solution(object):
    def maximumSwap(self, num):
        """
        :type num: int
        :rtype: int
        """
        nums = map(int, str(num))
        numt = sorted(nums, reverse=True)
        for (i, m), n in zip(enumerate(nums), numt):
            if m == n: continue
            maxv = max(nums[i + 1:])
            j = nums[i + 1:][::-1].index(maxv) + 1
            nums[i], nums[-j] = nums[-j], nums[i]
            break
        return int(''.join(map(str, nums)))

 

本文链接：http://bookshadow.com/weblog/2017/09/03/leetcode-maximum-swap/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码