LeetCode 0670. 最大交换

【LetMeFly】670.最大交换

力扣题目链接：https://leetcode.cn/problems/maximum-swap/

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

示例 1 :

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

示例 2 :

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

注意:

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

方法一：两次遍历

要想使得一次交换的结果尽量大，那么越大的数就要尽可能地越靠前。

因此，直接第一层循环枚举“尽可能前”的位置，第二层循环寻找之后的最大且尽可能靠后的元素。

如果找到了比前面大的元素，就交换二者，并返回结果。

• 时间复杂度$O({\log }^{2}num)$
• 空间复杂度$O(\log num)$

AC代码

C++

class Solution {
public:
    int maximumSwap(int num) {
        string s = to_string(num);
        for (int i = 0; i < s.size(); i++) {
            int locM = -1;
            char M = 0;
            for (int j = i + 1; j < s.size(); j++) {
                if (s[j] > s[i] && s[j] >= M) {
                    locM = j, M = s[j];
                }
            }
            if (locM != -1) {
                swap(s[i], s[locM]);
                return atoi(s.c_str());
            }
        }
        return atoi(s.c_str());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126826280