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 

复杂度对比

方法	时间复杂度	空间复杂度	适用场景
哈希表统计	O(n)	O(1)	通用字符集
固定数组	O(n)	O(1)	已知有限字符集
哈希表索引	O(n)	O(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. 更高效的哈希表索引存储法

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

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