【2022-09-13每日一题】670. 最大交换
2022-09-13
2分钟阅读时长
2022-09-13每日一题：670. 最大交换
- 难度：Medium
- 标签：贪心 、 数学
给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736 输出: 7236 解释: 交换数字2和数字7。
示例 2 :
输入: 9973 输出: 9973 解释: 不需要交换。
注意:
- 给定数字的范围是 [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
}