LeetCode Rust - 387 - 字符串中的第一个唯一字符

原题：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

解一，哈希表 §

遍历两次，第一次哈希表字符计数，第二次找到第一个只有一次计数的下标

字符串中只有小写字母，用数组替代哈希表可以获得更好的性能（减少哈希计算开销）

pub fn first_uniq_char(s: String) -> i32 {
	use std::collections::HashMap;
	let mut map = HashMap::<char, i32>::new();
	for char in s.chars() {
		let count = map.entry(char).or_insert(0);
		*count += 1;
	}
	for (i, char) in s.chars().into_iter().enumerate() {
		if *(map.get(&char).unwrap()) == 1 {
			return i as i32;
		}
	}
	return -1;
}

时间：$O(2n)=O(n)$

$n$ 为字符串长度

空间：$O(1)=O(S)$

$S$ 为字符集大小，题目中为 $S=26$

解二，队列 §

遍历字符串，对于每个字符 char

• 如果哈希表中不存在该字符
  • 在哈希表中记录该字符为 true
  • 将记录了字符和下标的元组 (char, index) 推入队尾
• 如果哈希表中存在该字符
  • 在哈希表中记录该字符为 false
  • 循环检查队列头部项
    • 如果在哈希表中标记为 false，取出丢弃
    • 如果在哈希表中标记为 true 或队列为空，结束循环
• 根据队列返回结果
  • 如果队列为空，则不存在只出现一次的字符，返回 -1
  • 否则队列中的头部项就是结果，返回其下标

pub fn first_uniq_char(s: String) -> i32 {
	use std::collections::HashMap;
	use std::collections::VecDeque;
	let mut map = HashMap::<char, bool>::new();
	let mut list = VecDeque::<(char, usize)>::new();
	for (i, char) in s.chars().into_iter().enumerate() {
		match map.get(&char) {
			Some(_) => {
				map.insert(char, false);
				while !list.is_empty() && !map.get(&(list.front().unwrap().0)).unwrap() {
					list.pop_front();
				}
			}
			None => {
				map.insert(char, true);
				list.push_back((char, i));
			}
		}
	}
 
	return if list.is_empty() { -1 } else { list.front().unwrap().1 as i32 };
}

时间：$O(n+2S)=O(n)$ 空间：$O(1)=O(2S)$

$n$ 为字符串长度 $S$ 为字符集大小，题目中为 $S=26$