【2022-09-13每日一题】670. 最大交换

2022-09-13
2分钟阅读时长

2022-09-13每日一题:670. 最大交换

  • 难度:Medium
  • 标签:贪心 、 数学

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

示例 1 :

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

示例 2 :

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

注意:

  1. 给定数字的范围是 [0, 108]
### 方法一:暴力枚举
func maximumSwap(num int) int {
    ans := num
    s := []byte(strconv.Itoa(num))
    for i := range s {
        for j := range s[:i] {
            s[i], s[j] = s[j], s[i]
            v, _ := strconv.Atoi(string(s))
            ans = max(ans, v)
            s[i], s[j] = s[j], s[i] // 还原
        }
    }
	return ans
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度:O(log^3*num)
  • 空间复杂度:O(lognum)

方法二:贪心

func maximumSwap(num int) int {
    nums := []byte(strconv.Itoa(num))
    n := len(nums)
    maxId, idx1, idx2 := n - 1, -1, -1
    for i := n-1; i >= 0; i-- {
        if nums[i] > nums[maxId] {
            maxId = i
        } else if nums[i] < nums[maxId] {
            idx1, idx2 = i, maxId
        }
    }
    if idx1 < 0 {
        return num
    }
    nums[idx1], nums[idx2] = nums[idx2], nums[idx1]
    num, _ = strconv.Atoi(string(nums))
    return num
}

复杂度分析

  • 时间复杂度:O(lognum)
  • 空间复杂度:O(lognum)

方法三:其他解法

func maximumSwap1(num int) int {
    mp := make([]int, 10)
    b := []byte(strconv.Itoa(num))
    for i, c := range b {
        mp[c - '0'] = i
    }
    LOOP:
    for i := 0; i < len(b); i++ {
        for k := 9; k > int(b[i] - '0'); k-- {
            if mp[k] > i {
                b[i], b[mp[k]] = b[mp[k]], b[i]
                break LOOP
            }
        }
    }
    num, _ = strconv.Atoi(string(b))
    return num
}

func maximumSwap(num int) int {
    mp := make([]int, 10)
    b := []byte(strconv.Itoa(num))
    // 记录每个数字出现的最后一次出现的下标
    for i, c := range b {
        mp[c - '0'] = i
    }
    // 从左向右扫描,找到当前位置右边的最大的数字并交换
    for i := 0; i < len(b); i++ {
        // 找最大,所以倒着找
        for k := 9; k > int(b[i] - '0'); k-- {
            if mp[k] > i {
                // 只允许交换一次,因此直接返回
                b[i], b[mp[k]] = b[mp[k]], b[i]
                num, _ = strconv.Atoi(string(b))
                return num
            }
        }
    }
    return num
}

LeetCode题库地址