【2022-12-03每日一题】1796. 字符串中第二大的数字[Easy]
2022-12-03
1分钟阅读时长
2022-12-03每日一题：1796. 字符串中第二大的数字
难度：Easy
标签：哈希表 、 字符串
给你一个混合字符串 s ，请你返回 s 中 第二大 的数字，如果不存在第二大的数字，请你返回 -1 。
混合字符串 由小写英文字母和数字组成。
示例 1：
输入：s = "dfa12321afd" 输出：2 解释：出现在 s 中的数字包括 [1, 2, 3] 。第二大的数字是 2 。
示例 2：
输入：s = "abc1111" 输出：-1 解释：出现在 s 中的数字只包含 [1] 。没有第二大的数字。
提示：
1 <= s.length <= 500s只包含小写英文字母和（或）数字。
方法一：直接遍历+双指针
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func secondHighest(s string) int {
first, second := -1, -1
for _, c := range s {
if unicode.IsDigit(c) {
num := int(c - '0')
if num > first {
first, second = num, first
} else if second < num && num < first {
// num < first 防止second 与 first 重复
second = num
}
}
}
return second
}
复杂度分析
时间复杂度：O(n)，其中 n 表示字符串的长度。我们只需遍历一遍字符串即可。
空间复杂度：O(1)。仅需常数个空间即可。
方法二：位运算
func secondHighest(s string) int {
mask := 0
for _, c := range s {
if c >= '0' && c <= '9' {
mask |= 1<<int(c-'0')
}
}
for i, cnt := 9, 0; i >= 0; i-- {
if mask>>i&1 == 1 {
cnt++
if cnt == 2 {
return i
}
}
}
return -1
}
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。