原文链接: https://leetcode-cn.com/problems/maximum-swap

英文原文

You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

 

Example 1:

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

Example 2:

Input: num = 9973
Output: 9973
Explanation: No swap.

 

Constraints:

• 0 <= num <= 108

中文题目

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1 :

输入: 2736
输出: 7236
解释: 交换数字2和数字7。

示例 2 :

输入: 9973
输出: 9973
解释: 不需要交换。

注意:

1. 给定数字的范围是 [0, 10⁸]

通过代码

官方题解

解决方法：

方法一：暴力法

数字最多只有 8 位，因此只有 28 个可用的互换。

算法：

• 我们将数字存储为长度为 $\text{len(num)}$ 的列表。对于位置为 $\text{(i, j)}$ 的每个候选交换，我们交换数字并记录组成的新数字是否大于当前答案，然后交换回来恢复原始数字。
• 唯一的细节可能是检查我们没有引入前导零。我们实际上不需要检查它，因为我们的原始数据没有。

[]
public class Solution {

    public int maximumSwap(int num) {
        String s = String.valueOf(num);
        int len = s.length();
        char[] charArray = s.toCharArray();
        int max = num;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                swap(charArray, i, j);
                max = Math.max(max, Integer.parseInt(new String(charArray)));
                swap(charArray, i, j);
            }
        }
        return max;
    }

    private void swap(char[] charArray, int index1, int index2) {
        char temp = charArray[index1];
        charArray[index1] = charArray[index2];
        charArray[index2] = temp;
    }
}

复杂度分析

• 时间复杂度：$O(N^3)$。其中 $N$ 是输入数字的总位数。对于每对数字，我们最多花费 $O(N)$ 的时间来比较最后的序列。
• 空间复杂度：$O(N)$，存储在 $\text{A}$ 中的信息。

方法二：贪心算法

算法：

• 我们将计算 $\text{last[d] = i}$，最后一次出现的数字 $\text{d}$（如果存在）的索引 $\text i$。
• 然后，从左到右扫描数字时，如果将来有较大的数字，我们将用最大的数字交换；如果有多个这样的数字，我们将用最开始遇到的数字交换。

[]
public class Solution {

    public int maximumSwap(int num) {
        String s = String.valueOf(num);
        int len = s.length();
        char[] charArray = s.toCharArray();

        // 记录每个数字出现的最后一次出现的下标
        int[] last = new int[10];
        for (int i = 0; i < len; i++) {
            last[charArray[i] - '0'] = i;
        }

        // 从左向右扫描，找到当前位置右边的最大的数字并交换
        for (int i = 0; i < len - 1; i++) {
            // 找最大，所以倒着找
            for (int d = 9; d > charArray[i] - '0'; d--) {
                if (last[d] > i) {
                    swap(charArray, i, last[d]);
                    // 只允许交换一次，因此直接返回
                    return Integer.parseInt(new String(charArray));
                }
            }
        }
        return num;
    }

    private void swap(char[] charArray, int index1, int index2) {
        char temp = charArray[index1];
        charArray[index1] = charArray[index2];
        charArray[index2] = temp;
    }
}

复杂度分析

• 时间复杂度：$O(N)$。其中，$N$ 是输入数字的总位数。每个数字最多只考虑一次。
• 空间复杂度：$O(1)$，$\text{last}$ 使用的额外空间最多只有 10 个。

统计信息

通过次数	提交次数	AC比率
20410	44904	45.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
拼接最大数	困难