网站建设 关于我们,安阳县属于哪个省哪个市,网站建设三站合一微信小程序,网站备案掉了文章目录 Tag题目来源解题思路方法一#xff1a;暴力法方法二#xff1a;贪心 写在最后 Tag
【暴力法】【贪心法】【数组】【2024-01-22】 题目来源
670. 最大交换 解题思路
本题的数据规模比较小#xff0c;暴力法也可以通过。以下将会介绍暴力法和本题最优法。
方法一… 文章目录 Tag题目来源解题思路方法一暴力法方法二贪心 写在最后 Tag
【暴力法】【贪心法】【数组】【2024-01-22】 题目来源
670. 最大交换 解题思路
本题的数据规模比较小暴力法也可以通过。以下将会介绍暴力法和本题最优法。
方法一暴力法
思路
对于整数 num 的十进制数位最长只有八位交换任意两个数位最多有 7 6 5 4 3 2 1 28 765432128 765432128
种不同的交换方法。我们统计这些交换后最大的 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 ( l o g 3 n u m ) O(log^3 \ num) O(log3 num) n u m num num 为给定的整数。 n u m num num 转化成十进制数的时间复杂度为 O ( l o g n u m ) O(log\ num) O(log num)一共有 O ( l o g 2 n u m ) O(log^2 \ num) O(log2 num) 种不同的交换方法。
空间复杂度 O ( l o g n u m ) O(log \ num) O(log num)。 n u m num num 转化成十进制数有 O ( l o g n u m ) O(log \ num) O(log num) 个数字需保存 n u m num 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 ( l o g n u m ) O(log \ num) O(log num) n u m num num 为给定的整数。 n u m num num 转化成十进制数有 O ( l o g n u m ) O(log\ num) O(log num) 个数需要遍历一次所有的数。
空间复杂度 O ( l o g n u m ) O(log \ num) O(log num)。 n u m num num 转化成十进制数有 O ( l o g n u m ) O(log\ num) O(log num) 个数需要保存 n u m num num 所有的数字。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
