leetcode
leetcode 1601 ~ 1650
字符串中第二大的数字

字符串中第二大的数字

难度:

标签:

题目描述

代码结果

运行时间: 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?
选择从数字9开始向下检查到0的原因是为了尽快找到最大的数字。一旦找到最大的数字,我们需要的只是第二大的数字。如果从0开始检查到9,则首先找到的较小数字并不有帮助,因为我们仍然需要继续检查更大的数字来确定哪个是最大和第二大的数字。从9到0的检查方式使得一旦找到最大数字后,下一个找到的数字即为第二大的,这样可以提高效率并简化逻辑。
🦆
在实现中使用`flag`来标记是否找到最大数字,是否有其他方式可以跟踪已经找到的最大和第二大的数字?
除了使用`flag`标记外,还可以使用一个列表来存储已找到的数字,列表最多存储两个元素,分别为最大和第二大的数字。每当找到一个新数字时,可以将其与列表中的数字进行比较并相应地更新列表,确保列表中第一个元素始终是最大的,第二个元素是第二大的。这种方法可以更直观地跟踪最大和第二大的数字,但可能稍微增加代码的复杂性。
🦆
使用`in`操作符来检查数字是否存在于字符串中,这种方法在字符串很长时效率如何?是否有更高效的扫描一次字符串来确定所有数字的方法?
使用`in`操作符来检查数字是否存在于字符串中可能在字符串很长时效率较低,因为每次检查都需要遍历整个字符串。一个更高效的方法是扫描字符串一次,使用一个布尔数组记录哪些数字出现过,数组的索引代表数字,值为布尔类型表示该数字是否出现过。这样,只需遍历一次字符串和一次布尔数组即可找出最大和第二大数字,从而提高效率。
🦆
如果字符串中数字的分布非常不均匀,例如在字符串末尾集中出现,这种方法处理上有何优势和劣势?
如果数字在字符串中的分布非常不均匀,特别是如果数字集中在末尾出现,使用`in`操作符的方法在检查到最后才可能找到需要的数字,这意味着每次检查都几乎需要遍历整个字符串。这在效率上是一个劣势。然而,如果使用之前提到的扫描一次字符串的方法,则数字分布的不均匀性不会影响效率,因为无论数字如何分布,都只需要遍历一次字符串,这是一个明显的优势。

相关问题