LeetCode如何找出字符串中的第一个唯一字符

# LeetCode如何找出字符串中的第一个唯一字符

## 问题描述

LeetCode第387题"First Unique Character in a String"要求我们找到字符串中第一个不重复的字符，并返回它的索引。如果不存在这样的字符，则返回-1。

**示例：**

输入: “leetcode” 输出: 0 解释: ‘l’是第一个唯一字符

输入: “loveleetcode” 输出: 2 解释: ‘v’是第一个唯一字符

## 解决方案分析

### 方法一：哈希表统计频率

#### 算法思路
1. 第一次遍历字符串，使用哈希表记录每个字符出现的次数
2. 第二次遍历字符串，找到第一个出现次数为1的字符
3. 时间复杂度O(n)，空间复杂度O(1)（因为字母表大小固定）

#### Python实现
```python
def firstUniqChar(s: str) -> int:
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    
    for i, char in enumerate(s):
        if freq[char] == 1:
            return i
    
    return -1

方法二：使用固定数组优化

算法优化

当字符集有限时（如小写字母），可以用固定大小的数组代替哈希表，减少哈希计算开销。

Python实现

def firstUniqChar(s: str) -> int:
    count = [0] * 26  # 假设只有小写字母
    for char in s:
        count[ord(char) - ord('a')] += 1
    
    for i, char in enumerate(s):
        if count[ord(char) - ord('a')] == 1:
            return i
    
    return -1

方法三：哈希表存储索引

进阶思路

可以进一步优化，在哈希表中存储字符的索引，遇到重复时标记为特殊值（如-1），这样只需一次遍历即可完成统计。

Python实现

def firstUniqChar(s: str) -> int:
    index_map = {}
    for i, char in enumerate(s):
        if char in index_map:
            index_map[char] = -1
        else:
            index_map[char] = i
    
    min_index = float('inf')
    for char in index_map:
        if index_map[char] != -1 and index_map[char] < min_index:
            min_index = index_map[char]
    
    return min_index if min_index != float('inf') else -1

复杂度对比

边界条件测试

良好的解决方案应该考虑以下边界情况： 1. 空字符串："" → 应返回-1 2. 全部重复字符："aabbcc" → 应返回-1 3. 唯一字符在最后："aabbc" → 应返回4 4. 大小写敏感："aA" → 应返回0（如果题目区分大小写）

实际应用场景

这种算法在实际开发中有广泛用途： 1. 日志分析中查找首个异常事件 2. 数据流中检测首个唯一元素 3. 编译器词法分析时处理特殊符号 4. 网络安全领域检测异常访问模式

算法扩展思考

变种问题1：流数据中的首个唯一字符

当数据以流形式到达无法存储整个字符串时，需要结合队列和哈希表设计解决方案：

from collections import deque

class FirstUnique:
    def __init__(self):
        self.queue = deque()
        self.freq = {}
    
    def add(self, char: str) -> None:
        if char in self.freq:
            self.freq[char] += 1
        else:
            self.freq[char] = 1
            self.queue.append(char)
    
    def getFirstUnique(self) -> str:
        while self.queue:
            char = self.queue[0]
            if self.freq[char] == 1:
                return char
            self.queue.popleft()
        return -1

变种问题2：找出所有唯一字符

如果需要返回所有唯一字符，只需修改过滤条件：

def allUniqChars(s: str) -> List[int]:
    freq = {}
    res = []
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    
    for i, char in enumerate(s):
        if freq[char] == 1:
            res.append(i)
    
    return res

性能优化技巧

1. 提前终止：在第二次遍历时，找到第一个唯一字符即可立即返回
2. 内存优化：对于已知字符集（如ASCII），使用数组比哈希表更节省内存
3. 并行处理：超长字符串可考虑分块并行统计频率

不同语言实现对比

Java实现（使用LinkedHashMap保持插入顺序）

public int firstUniqChar(String s) {
    Map<Character, Integer> map = new LinkedHashMap<>();
    for (char c : s.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    for (int i = 0; i < s.length(); i++) {
        if (map.get(s.charAt(i)) == 1) {
            return i;
        }
    }
    return -1;
}

JavaScript实现（利用indexOf方法）

function firstUniqChar(s) {
    for (let i = 0; i < s.length; i++) {
        if (s.indexOf(s[i]) === s.lastIndexOf(s[i])) {
            return i;
        }
    }
    return -1;
}

总结

解决”找出字符串中第一个唯一字符”的问题，我们探索了多种方法： 1. 最直观的哈希表频率统计法 2. 针对有限字符集的数组优化法 3. 更高效的哈希表索引存储法

关键点在于理解问题本质，选择合适的数据结构，并考虑实际应用中的各种边界条件。该问题的解决思路可以扩展到许多类似的字符串处理场景中。

最终建议：在面试或实际应用中，推荐使用固定数组法（当字符集有限时）或基础哈希表法，它们在时间复杂度和代码可读性之间取得了良好平衡。 “`