跳转至

1796. 字符串中第二大的数字

题目描述

给你一个混合字符串 s ,请你返回 s 中 第二大 的数字,如果不存在第二大的数字,请你返回 -1 。

混合字符串 由小写英文字母和数字组成。

 

示例 1:

输入:s = "dfa12321afd"
输出:2
解释:出现在 s 中的数字包括 [1, 2, 3] 。第二大的数字是 2 。

示例 2:

输入:s = "abc1111"
输出:-1
解释:出现在 s 中的数字只包含 [1] 。没有第二大的数字。

 

提示:

  • 1 <= s.length <= 500
  • s 只包含小写英文字母和(或)数字。

解法

方法一:一次遍历

我们定义 $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)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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
}

评论