leetcode
leetcode 2001 ~ 2050
第一个出现两次的字母

第一个出现两次的字母

难度:

标签:

题目描述

代码结果

运行时间: 22 ms, 内存: 15.8 MB


/*
 * 思路:
 * 使用Java Stream API来实现。
 * 将字符串转换为字符流,使用一个Set集合来追踪已经遇到的字符。
 * 过滤出第一个已经存在于Set集合中的字符并返回。
 */
import java.util.Set;
import java.util.HashSet;
import java.util.Optional;

public class Solution {
    public char repeatedCharacter(String s) {
        Set<Character> seen = new HashSet<>();
        Optional<Character> result = s.chars() // 将字符串转换为字符流
            .mapToObj(c -> (char)c) // 将每个int字符转换为Character对象
            .filter(c -> !seen.add(c)) // 过滤出第一个已经存在于Set集合中的字符
            .findFirst(); // 返回第一个匹配的字符
        return result.orElse(' '); // 按照题意,s一定包含至少一个重复字母,因此这里不会到达。
    }
}

解释

方法:

题解通过使用哈希表来记录字符串中每个字符的出现情况。遍历字符串的每个字符,对于每个字符,检查它是否已经在哈希表中存在。如果存在,说明该字符已经至少出现了两次,直接返回这个字符作为答案。如果不存在,则将该字符加入哈希表。这种方法能够在找到第一个重复字符时立即停止并返回结果。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么选择哈希表作为这个问题的数据结构?有没有其他数据结构可以实现相同的功能?
哈希表(或字典)被选择用于此问题是因为它提供了平均时间复杂度为O(1)的快速查找、插入和删除操作,这使得检查字符是否已出现过变得非常高效。其他数据结构比如数组可以用于存储字符计数,但对于非ASCII字符,这可能不太高效或需要额外的空间。集合可以用来检查重复,但不如哈希表方便在发现重复时立即停止处理。
🦆
哈希表中的键值对是如何更新的?具体是怎样判断和处理字符第二次出现的?
在题解中,哈希表初始化为空。每次遍历到一个字符时,首先检查这个字符是否已经在哈希表中。这通过调用 `get` 方法实现,如果返回值非空,则说明字符已出现过。在这种情况下,由于我们要找的是第一个重复的字符,即刻返回这个字符。如果字符不在哈希表中,则将该字符加入哈希表并标记为出现一次。
🦆
如果字符串中的某个字符第二次出现的位置非常靠后,这种情况下算法的效率如何?
即使字符重复出现的位置非常靠后,算法仍需遍历每个字符直至找到重复字符。因此,最坏情况下的时间复杂度是O(n),其中n是字符串的长度。虽然这可能导致在某些情况下算法运行时间较长,但对于任意长度的字符串,这种方法仍然是效率较高的。
🦆
题解提到在找到第一个重复字符时立即停止并返回结果,这种策略是否总是能保证找到第一个按题目要求的字符?
是的,这种策略能够保证找到第一个按题目要求的字符。算法通过逐一检查每个字符并记录其出现情况,确保一旦发现任何字符第二次出现即停止搜索。这意味着返回的第一个重复字符确实是按照字符串中字符出现的顺序第一个重复的。

相关问题