刷题

第一个只出现一次的字符

scorlw 发布于

第一个只出现一次的字符

关键词：哈希表、有序哈希表

题目描述

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例 1：

1
2
3
4
5
s = "abaccdeff"
返回 "b"

s = "" 
返回 " "

解法

本题考察 哈希表 的使用，本文介绍 “哈希表” 和 “有序哈希表” 两种解法。
其中，在字符串很长时， “有序哈希表” 解法理论上效率更高。

解法一：

思路：

哈希表：

  1. 遍历字符串 s ，使用哈希表统计 “各字符数量是否 >1 ”。
  2. 再遍历字符串 s ，在哈希表中找到首个 “数量为 1 的字符”，并返回。

算法流程：

  1. 哈希表：初始化大小为26，初始值为0的哈希表；
  2. 遍历s，统计各个字符的数量；
  3. 再次遍历s，返回第一个数量为1的字符；
  4. 如果没有返回，那么返回空格。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
char firstUniqChar(string s)
{
    vector<int> hashs(26, 0);
    string res = "";
    for (char c : s)
    {
        hashs[c - 'a']++;
    }
    for (char c : s)
    {
        if (hashs[c - 'a'] == 1)
        {
            res.push_back(c);
        }
    }
    if (res.empty())
        res = " ";
    return res[0];
}

解法二：

思路：

有序哈希表：

在哈希表的基础上，有序哈希表中的键值对是 按照插入顺序排序 的。基于此，可通过遍历有序哈希表，实现搜索首个 “数量为 1 的字符”。

哈希表是 去重 的，即哈希表中键值对的数量 ≤ 字符串 s 的长度。因此，相比于方法一，方法二减少了第二轮遍历的循环次数。当字符串很长（重复字符很多）时，方法二则效率更高。

复杂度分析：

时间和空间复杂度均与 “方法一” 相同，而具体分析时间复杂度：

方法一 O(2N) ： N 为字符串 s 的长度；需遍历 s 两轮；
方法二 O(N) ：遍历 s 一轮，遍历 dic 一轮。因为dic的长度<=26 ,最多就是全部字母都有。所以遍历dic 是O(1)常量

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//本地可以，力扣不行，原因未找到
char firstUniqChar(const string s)
{
	if (s.empty())	return ' ';
	unordered_map<char, int> ch;
    stack<char> st;
	int id=0;
	while (id < s.size())
	{
		if (ch.find(s[id]) == ch.end())	ch[s[id]] = 1;
		else ch[s[id]] += 1;
		id++;
	}
	auto it = ch.begin();

    while (it != ch.end())
    {
        if((*it).second == 1) st.push((*it).first);
        it++;
    }

    return st.empty() ? ' ' : st.top();
}

知识点

  1. unordered_map的使用，特性，count等函数；
  2. 哈希表和有序哈希表的思路。