LeetCode 670. 最大交换

目录

一、题目

1、题目描述

2、接口描述

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

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

示例 1 :

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

2、接口描述

?

class Solution {
public:
    int maximumSwap(int num) {

    }
};

3、原题链接

670. 最大交换

---

二、解题报告

1、思路分析

贪心的考虑，肯定优先把高位跟大数字交换，我们从高位遍历，如果高位右边有数组比高位大，那么和右边最大数字且最靠右的那个交换即可

2、复杂度

时间复杂度：O(log num)?空间复杂度：O(log num)

3、代码详解

?

class Solution {
public:

    int maximumSwap(int num) {
        int d[10] , pre[10]{0} , n = 0;
        while(num) {
            d[++n] = num % 10 , num /= 10;
            pre[n + 1] = d[pre[n]] >= d[n] ? pre[n] : n; 
        }
        for(int i = n ; i >= 1 ; i--)
            if(d[pre[i]] > d[i]){
                swap(d[i] , d[pre[i]]);
                break;
            }
        for(int i = n ; i >= 1 ; i--)
            num = (num << 3) + (num << 1) + d[i];
        return num;
    }
};