字符串中第二大的数字
难度:
标签:
题目描述
代码结果
运行时间: 23 ms, 内存: 16.0 MB
/*
* 思路:
* 1. 使用流操作提取字符串中的数字字符。
* 2. 使用集合去重。
* 3. 将集合转换为列表并排序。
* 4. 返回排序后列表的第二个最大数字,如果不存在则返回-1。
*/
import java.util.*;
import java.util.stream.Collectors;
public class SecondLargestDigitStream {
public static int secondHighest(String s) {
List<Integer> digits = s.chars()
.filter(Character::isDigit)
.map(c -> c - '0')
.distinct()
.sorted()
.boxed()
.collect(Collectors.toList());
if (digits.size() < 2) {
return -1;
} else {
return digits.get(digits.size() - 2);
}
}
public static void main(String[] args) {
System.out.println(secondHighest("dfa12321afd")); // 输出 2
System.out.println(secondHighest("abc1111")); // 输出 -1
}
}
解释
方法:
该题解采用的方法是从最大的数字开始向下检查每个数字是否存在于字符串中。首先,从数字9开始,逐一检查到数字0,利用Python的'in'操作符来确认数字是否出现在字符串中。在此过程中,使用一个布尔型标记变量`flag`来记录是否已经找到了第一个最大的数字。当找到第一个最大的数字时,将`flag`设置为True。如果在找到第一个最大数字后再次找到数字,则此数字即为第二大的数字,直接返回该数字。如果遍历完成后未找到两个不同的数字,则返回-1。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择从数字9开始向下检查到0,而不是从0开始检查到9?
▷🦆
在实现中使用`flag`来标记是否找到最大数字,是否有其他方式可以跟踪已经找到的最大和第二大的数字?
▷🦆
使用`in`操作符来检查数字是否存在于字符串中,这种方法在字符串很长时效率如何?是否有更高效的扫描一次字符串来确定所有数字的方法?
▷🦆
如果字符串中数字的分布非常不均匀,例如在字符串末尾集中出现,这种方法处理上有何优势和劣势?
▷