【每日一题】最大交换-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日一题】最大交换。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Tag

【暴力法】【贪心法】【数组】【2024-01-22】

题目来源

670. 最大交换

【每日一题】最大交换,LeetCode每日一题,暴力法,贪心,字符串,2024-01-22

解题思路

本题的数据规模比较小，暴力法也可以通过。以下将会介绍暴力法和本题最优法。

方法一：暴力法

思路

对于整数 num 的十进制数位最长只有八位，交换任意两个数位最多有

$7 + 6 + 5 + 4 + 3 + 2 + 1 = 28$

种不同的交换方法。我们统计这些交换后最大的 int 型整数。

算法

class Solution {
public:
    int maximumSwap(int num) {
        string str = to_string(num);
        int n = str.size();
        int maxNum = num;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                swap(str[i], str[j]);
                maxNum = max(maxNum, stoi(str));
                swap(str[i], str[j]);
            }
        }
        return maxNum;
    }
};

复杂度分析

时间复杂度： $O(log^3 \ num)$ ， $n u m$ 为给定的整数。 $n u m$ 转化成十进制数的时间复杂度为 $O(log\ num)$ ，一共有 $O(log^2 \ num)$ 种不同的交换方法。

空间复杂度： $\ num)$ 。 $n u m$ 转化成十进制数有 $\ num)$ 个数字，需保存 $n u m$ 所有的数字。

方法二：贪心

思路

对于 num 的理想最大数：每个数位上的数字都比其后的任意数位上的数字大，否则就要找到排在其后面的最大数，与之交换。

算法

在具体实现中，我们倒序遍历数字字符串 numArray，记录当前遍历到的最大字符位置 mxIdx。如果当前数字字符 numArray[i] 右边有比它大的，即有 numArray[i] < numArray[mxIdx]，则将 i 和 mxIdx 位置分别记录为 idx1 = i 和 idx2 = mxIdx。

我们最终需要交换的是靠近左侧的 idx1 和 idx2。

class Solution {
public:
    int maximumSwap(int num) {
        string numArray = to_string(num);
        int n = numArray.size();
        int mxIdx = n - 1;
        int idx1 = -1, idx2 = -1;
        for(int i = n-2; i >= 0; --i) {
            if(numArray[i] > numArray[mxIdx]) {      // numArray[i] 是目前最大的数字
                mxIdx = i;
            }
            else if(numArray[i] < numArray[mxIdx]) { // numArray[i] 右边有比它大的
                idx1 = i;
                idx2 = mxIdx;
            }
        }

        if(idx1 >= 0) {
            swap(numArray[idx1], numArray[idx2]);
            return stoi(numArray);
        }
        return num;
    }
};

复杂度分析

时间复杂度： $\ num)$ ， $n u m$ 为给定的整数。 $n u m$ 转化成十进制数有 $O(log\ num)$ 个数，需要遍历一次所有的数。