题目描述
给你一个混合字符串 s ，请你返回 s 中 第二大 的数字，如果不存在第二大的数字，请你返回 -1 。
混合字符串 由小写英文字母和数字组成。
示例 1：
输入：s = "dfa12321afd"
输出：2
解释：出现在 s 中的数字包括 [1, 2, 3] 。第二大的数字是 2 。
示例 2：
输入：s = "abc1111"
输出：-1
解释：出现在 s 中的数字只包含 [1] 。没有第二大的数字。
提示：
1 <= s.length <= 500s 只包含小写英文字母和（或）数字。
解法
方法一：一次遍历
我们定义 $a$ 和 $b$ 分别表示字符串中出现的最大数字和第二大数字，初始时 $a = b = -1$。
遍历字符串 $s$，如果当前字符是数字，我们将其转换为数字 $v$，如果 $v \gt a$，说明 $v$ 是当前出现的最大数字，我们将 $b$ 更新为 $a$，并将 $a$ 更新为 $v$；如果 $v \lt a$，说明 $v$ 是当前出现的第二大数字，我们将 $b$ 更新为 $v$。
遍历结束，返回 $b$ 即可。
时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$。
| class Solution:
def secondHighest(self, s: str) -> int:
a = b = -1
for c in s:
if c.isdigit():
v = int(c)
if v > a:
a, b = v, a
elif b < v < a:
b = v
return b
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution {
public int secondHighest(String s) {
int a = -1, b = -1;
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
int v = c - '0';
if (v > a) {
b = a;
a = v;
} else if (v > b && v < a) {
b = v;
}
}
}
return b;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public:
int secondHighest(string s) {
int a = -1, b = -1;
for (char& c : s) {
if (isdigit(c)) {
int v = c - '0';
if (v > a) {
b = a, a = v;
} else if (v > b && v < a) {
b = v;
}
}
}
return b;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | func secondHighest(s string) int {
a, b := -1, -1
for _, c := range s {
if c >= '0' && c <= '9' {
v := int(c - '0')
if v > a {
b, a = a, v
} else if v > b && v < a {
b = v
}
}
}
return b
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | function secondHighest(s: string): number {
let first = -1;
let second = -1;
for (const c of s) {
if (c >= '0' && c <= '9') {
const num = c.charCodeAt(0) - '0'.charCodeAt(0);
if (first < num) {
[first, second] = [num, first];
} else if (first !== num && second < num) {
second = num;
}
}
}
return second;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | impl Solution {
pub fn second_highest(s: String) -> i32 {
let mut first = -1;
let mut second = -1;
for c in s.as_bytes() {
if char::is_digit(*c as char, 10) {
let num = (c - b'0') as i32;
if first < num {
second = first;
first = num;
} else if num < first && second < num {
second = num;
}
}
}
second
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | int secondHighest(char* s) {
int first = -1;
int second = -1;
for (int i = 0; s[i]; i++) {
if (isdigit(s[i])) {
int num = s[i] - '0';
if (num > first) {
second = first;
first = num;
} else if (num < first && second < num) {
second = num;
}
}
}
return second;
}
|
方法二：位运算
我们可以用一个整数 $mask$ 来标识字符串中出现的数字，其中 $mask$ 的第 $i$ 位表示数字 $i$ 是否出现过。
遍历字符串 $s$，如果当前字符是数字，我们将其转换为数字 $v$，将 $mask$ 的第 $v$ 个二进制位的值置为 $1$。
最后，我们从高位向低位遍历 $mask$，找到第二个为 $1$ 的二进制位，其对应的数字即为第二大数字。如果不存在第二大数字，返回 $-1$。
时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$。
| class Solution:
def secondHighest(self, s: str) -> int:
mask = reduce(or_, (1 << int(c) for c in s if c.isdigit()), 0)
cnt = 0
for i in range(9, -1, -1):
if (mask >> i) & 1:
cnt += 1
if cnt == 2:
return i
return -1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public int secondHighest(String s) {
int mask = 0;
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
mask |= 1 << (c - '0');
}
}
for (int i = 9, cnt = 0; i >= 0; --i) {
if (((mask >> i) & 1) == 1 && ++cnt == 2) {
return i;
}
}
return -1;
}
}
|
| class Solution {
public:
int secondHighest(string s) {
int mask = 0;
for (char& c : s)
if (isdigit(c)) mask |= 1 << c - '0';
for (int i = 9, cnt = 0; ~i; --i)
if (mask >> i & 1 && ++cnt == 2) return i;
return -1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | 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
}
|