题解 | 首个重复字符

解题思路

使用哈希表记录字符出现情况：
- 遍历字符串
- 记录每个字符的出现次数
- 再次遍历找到第一个重复的字符
优化方案：
- 使用数组代替哈希表（更高效）
- 使用布尔数组标记是否出现
- 第一次遍历就能找到结果

代码

cpp
java
python

class FirstRepeat {
public:
    char findFirstRepeat(string A, int n) {
        vector<bool> seen(256, false);  // 假设ASCII字符
        
        // 遍历字符串
        for(char c : A) {
            // 如果字符已经出现过，返回该字符
            if(seen[c]) {
                return c;
            }
            // 标记字符已出现
            seen[c] = true;
        }
        
        return ' ';  // 不会执行到这里，因为题目保证有重复字符
    }
};

import java.util.*;

public class FirstRepeat {
    public char findFirstRepeat(String A, int n) {
        boolean[] seen = new boolean[256];  // 假设ASCII字符
        
        // 遍历字符串
        for(char c : A.toCharArray()) {
            // 如果字符已经出现过，返回该字符
            if(seen[c]) {
                return c;
            }
            // 标记字符已出现
            seen[c] = true;
        }
        
        return ' ';  // 不会执行到这里，因为题目保证有重复字符
    }
}


class FirstRepeat:
    def findFirstRepeat(self, A, n):
        # init set to store seen chars
        seen = set()
        
        # iterate through string
        for c in A:
            if c in seen:
                return c
            seen.add(c)
        
        return ' '

算法及复杂度

算法：哈希表/数组标记
时间复杂度： $\mathcal{O}(n)$ ，其中 $n$ 为字符串长度
空间复杂度： $\mathcal{O}(1)$ ，使用固定大小的数组/集合