【每日一题】最大交换

Tag

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

题目来源

670. 最大交换

解题思路

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

方法一：暴力法

思路

对于整数 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(lo{g}^{3}num)$，$num$ 为给定的整数。$num$ 转化成十进制数的时间复杂度为 $O(lognum)$，一共有 $O(lo{g}^{2}num)$ 种不同的交换方法。

空间复杂度：$O(lognum)$。$num$ 转化成十进制数有 $O(lognum)$ 个数字，需保存 $num$ 所有的数字。

方法二：贪心

思路

对于 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;
    }
};

复杂度分析

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

空间复杂度：$O(lognum)$。$num$ 转化成十进制数有 $O(lognum)$ 个数，需要保存 $num$ 所有的数字。

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。