Easy

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路

解题思路

这道题要求找到字符串中第二大的数字，核心是要理解"第二大"意味着需要去重，即相同的数字只算一个。

方法一：集合去重 + 排序（推荐）

  1. 遍历字符串，提取所有数字字符并存入集合自动去重
  2. 将集合转为列表并排序，取第二大的元素
  3. 如果数字种类少于2种，返回-1

方法二：维护两个变量

  1. 用两个变量 first 和 second 分别记录最大和第二大的数字
  2. 遍历字符串时动态更新这两个值
  3. 需要注意去重逻辑，避免相同数字影响结果

方法三：数组标记 由于数字字符只有0-9共10个，可以用布尔数组标记出现过的数字，然后从大到小找第二个出现的数字。

三种方法中，集合去重的方式最直观易懂，代码简洁，是推荐解法。时间复杂度都是O(n)，空间复杂度O(1)（因为数字字符最多10个）。

代码实现

class Solution {
public:
    int secondHighest(string s) {
        set<int> digits;
        for (char c : s) {
            if (isdigit(c)) {
                digits.insert(c - '0');
            }
        }
        if (digits.size() < 2) return -1;
        auto it = digits.rbegin();
        ++it;
        return *it;
    }
};

class Solution:
    def secondHighest(self, s: str) -> int:
        digits = set()
        for c in s:
            if c.isdigit():
                digits.add(int(c))
        
        if len(digits) < 2:
            return -1
        
        sorted_digits = sorted(digits, reverse=True)
        return sorted_digits[1]

public class Solution {
    public int SecondHighest(string s) {
        HashSet<int> digits = new HashSet<int>();
        foreach (char c in s) {
            if (char.IsDigit(c)) {
                digits.Add(c - '0');
            }
        }
        
        if (digits.Count < 2) return -1;
        
        var sortedDigits = digits.OrderByDescending(x => x).ToList();
        return sortedDigits[1];
    }
}

var secondHighest = function(s) {
    const digits = new Set();
    for (let c of s) {
        if (c >= '0' && c <= '9') {
            digits.add(parseInt(c));
        }
    }
    
    if (digits.size < 2) return -1;
    
    const sortedDigits = Array.from(digits).sort((a, b) => b - a);
    return sortedDigits[1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历整个字符串，n为字符串长度
空间复杂度O(1)数字字符最多10个，集合大小为常数级别

相关题目