342-Leetcode 字符串中的第一个唯一字符

方法一：使用哈希表存储频数

class Solution 
{
    
public:
	int firstUniqChar(string s) 
	{
    
		unordered_map<char, int> map;
		for (auto& ch : s)
		{
    
			++map[ch];
		}
		int len = s.size();
		for (int i = 0; i < len; ++i)
		{
    
			if (map[s[i]] == 1)
			{
    
				return i;
			}
		}
		return -1;
	}
};
int main()
{
    
	Solution A;
	cout << A.firstUniqChar("leetlcode") << endl;
	return 0;
}

时间复杂度：O(n)，其中 n 是字符串 s 的长度。我们需要进行两次遍历。
空间复杂度：O(∣Σ∣)，其中 Σ 是字符集，在本题中 s 只包含小写字母，因此 26∣Σ∣≤26。我们需要 O(∣Σ∣) 的空间存储哈希映射

方法二：使用哈希表存储索引

第二次遍历是遍历哈希表，而不是遍历字符串，会相比较于方法一来说效率更高，时间复杂度会降低

对于哈希映射中的每一个键值对，键表示一个字符，值表示它的首次出现的索引（如果该字符只出现一次）或者 -1（如果该字符出现多次）。当我们第一次遍历字符串时，设当前遍历到的字符为 c，如果 c 不在哈希映射中，我们就将 c 与它的索引作为一个键值对加入哈希映射中，否则我们将 c 在哈希映射中对应的值修改为 -1

在第一次遍历结束后，我们只需要再遍历一次哈希映射中的所有值，找出其中不为 -1 的最小值，即为第一个不重复字符的索引。如果哈希映射中的所有值均为 -1，我们就返回 -1

class Solution 
{
    
public:
	int firstUniqChar(string s) 
	{
    
		unordered_map<char, int> map;
		int len = s.size();
		for (int i = 0; i < len; ++i)
		{
    
			if (map.count(s[i]))
			{
    
				map[s[i]] = -1;
			}
			else
			{
    
				map[s[i]] = i;
			}
		}
		int tmp = len;
		for (auto [_, pos] : map)
		{
    
			if (pos != -1 && pos < tmp)
			{
    
				tmp = pos;
			}
		}
		if (tmp == len)
		{
    
			tmp = -1;
		}
		return tmp;
	}
};
int main()
{
    
	Solution A;
	cout << A.firstUniqChar("leetlcode") << endl;
	return 0;
}

时间复杂度：O(n)，其中 n 是字符串 s 的长度。第一次遍历字符串的时间复杂度为 O(n)，第二次遍历哈希映射的时间复杂度为 O(∣Σ∣)，由于 ss 包含的字符种类数一定小于 s 的长度，因此 O(∣Σ∣) 在渐进意义下小于 O(n)，可以忽略
空间复杂度：O(∣Σ∣)，其中 Σ 是字符集，在本题中 s 只包含小写字母，因此 ∣Σ∣≤ 26。我们需要 O(∣Σ∣) 的空间存储哈希映射

方法三：队列

我们也可以借助队列找到第一个不重复的字符。队列具有「先进先出」的性质，因此很适合用来找出第一个满足某个条件的元素

具体地，我们使用与方法二相同的哈希映射，并且使用一个额外的队列，按照顺序存储每一个字符以及它们第一次出现的位置。当我们对字符串进行遍历时，设当前遍历到的字符为 c，如果 c 不在哈希映射中，我们就将 c 与它的索引作为一个二元组放入队尾，否则我们就需要检查队列中的元素是否都满足「只出现一次」的要求，即我们不断地根据哈希映射中存储的值（是否为 −1）选择弹出队首的元素，直到队首元素「真的」只出现了一次或者队列为空

在遍历完成后，如果队列为空，说明没有不重复的字符，返回 −1，否则队首的元素即为第一个不重复的字符以及其索引的二元组

注意：在维护队列时，我们使用了「延迟删除」这一技巧。也就是说，即使队列中有一些字符出现了超过一次，但它只要不位于队首，那么就不会对答案造成影响，我们也就可以不用去删除它。只有当它前面的所有字符被移出队列，它成为队首时，我们才需要将它移除

class Solution 
{
    
public:
	int firstUniqChar(string s) 
	{
    
		unordered_map<char, int> map;
		queue<pair<char, int>> qu;
		int len = s.size();
		for (int i = 0; i < len; ++i)
		{
    
			if (!map.count(s[i]))
			{
    
				map[s[i]] = i;
				qu.emplace(s[i], i);
			}
			else
			{
    
				map[s[i]] = -1;
				while (!qu.empty() && map[qu.front().first] == -1)
				{
    
					qu.pop();
				}
			}
		}
		return qu.empty() ? -1 : qu.front().second;
	}
};
int main()
{
    
	Solution A;
	cout << A.firstUniqChar("leetlcode") << endl;
	return 0;
}

时间复杂度：O(n)，其中 n 是字符串 s 的长度。遍历字符串的时间复杂度为 O(n)，而在遍历的过程中我们还维护了一个队列，由于每一个字符最多只会被放入和弹出队列最多各一次，因此维护队列的总时间复杂度为 O(∣Σ∣)，由于 s 包含的字符种类数一定小于 s 的长度，因此 O(∣Σ∣) 在渐进意义下小于 O(n)，可以忽略

空间复杂度：O(∣Σ∣)，其中 Σ 是字符集，在本题中 s 只包含小写字母，因此 ∣Σ∣≤26。我们需要 O(∣Σ∣) 的空间存储哈希映射以及队列