剑指offer（专项突破版）5.3 哈希表的应用
分析
遍历第一个字符串，使用数组作为哈希表，字母出现则+1；然后遍历第二个字符串，字母出现则-1；最后判断数组中的值是否全为0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
bool isAnagram(string s, string t) {
int m = s.length();
int n = t.length();
if(m != n || s == t){
return false;
}
vector<int> hash(26);
for(int i = 0; i < m; i++){
hash[s[i]-97]++;
}
for(int i = 0; i < n; i++){
hash[t[i]-97]--;
}
for(int i = 0; i < 26; i++){
if(hash[i]){
return false;
}
}
return true;
}
};
|
进阶
如果输入字符串包含unicode字符怎么办？
一个ASCII码字符的长度为8位，所以ASCII码字符集只能包含256个不同的字符，中文及很多语言的字符集都远远超过这个数字。为了包含更多的字符，需要其他编码的字符集，目前使用最多的是Unicode编码。一个Unicode的字符的长度为16位，这样就能表示65536个字符。
使用真正的哈希表unordered_map<char,int>记录。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
bool isAnagram(string s, string t) {
int m = s.length();
int n = t.length();
if(m != n || s == t){
return false;
}
unordered_map<char,int> hash;
for(int i = 0; i < m; i++){
hash[s[i]]++;
}
for(int i = 0; i < n; i++){
hash[t[i]]--;
}
unordered_map<char, int>::iterator iter;
for(iter = hash.begin(); iter != hash.end(); iter++){
if(iter->second){
return false;
}
}
return true;
}
};
|
方法1：将单词的字母排序
把一组变位词映射到同一个单词。由于互为变位词的单词的字母出现的次数分别相同，因此如果把单词中的字母排序就会得到相同的字符串。例如，把”eat”、”tea”和”ate”的字母按照字母表顺序排序都得到字符串”aet”。
因此，可以定义一个哈希表，哈希表的键是把单词字母排序得到的字符串，而值为一组变位词。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
unordered_map<string, vector<string>> hash;
for(int i = 0; i < strs.size(); i++){
string key = strs[i];
sort(key.begin(), key.end());
hash[key].push_back(strs[i]);
}
unordered_map<string, vector<string>>::iterator iter;
for(iter = hash.begin(); iter != hash.end(); iter++){
res.push_back(iter->second);
}
return res;
}
};
|
- 如果每个单词平均有m个字母，排序一个单词需要O（mlogm）的时间。假设总共有n个单词，该算法总的时间复杂度是O（nmlogm）。
- 使用了一个哈希表来存储排序后的字符串和对应的字符串列表，哈希表的空间复杂度为 O(n)。最终返回的结果 res 也需要 O(n) 的空间来存储结果。因此，总的空间复杂度为 O(n)。
方法2：计数
由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。
由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为 262626 的数组记录每个字母出现的次数。需要注意的是，在使用数组作为哈希表的键时，不同语言的支持程度不同，因此不同语言的实现方式也不同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
string getString(string s){
string str(26,'0');
for(char c:s){
str[c-'a']++;
}
return str;
}
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
unordered_map<string, vector<string>> hash;
for(int i = 0; i < strs.size(); i++){
string key = getString(strs[i]);
hash[key].push_back(strs[i]);
}
unordered_map<string, vector<string>>::iterator iter;
for(iter = hash.begin(); iter != hash.end(); iter++){
res.push_back(iter->second);
}
return res;
}
};
|
- 时间复杂度对于每个字符串，生成字符串表示需要遍历字符串一次，时间复杂度为 O(m)。因此，在遍历输入字符串数组时，对每个字符串执行这样的操作，所以总的时间复杂度是 O(mn)，其中 n 是字符串数组的长度，m是字符串的平均长度。
- 空间复杂度：和第一种方法相同，O(n)。
分析
直接的想法是把字母顺序存到哈希表里，键为字母，值为其顺序。然后检查每一个字符串，是否满足这个顺序。怎么检查，逐个字母判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
private:
int hash[26];
public:
bool isSorted(string s, string t){
int m = s.length();
int n = t.length();
int i = 0;
while(i < min(m,n) && s[i] == t[i]){
i++;
}
if(i == m){
return true;
}
if(i == n){
return false;
}
if(hash[s[i]-'a'] <= hash[t[i]-'a']){
return true;
}
else{
return false;
}
}
bool isAlienSorted(vector<string>& words, string order) {
for(int i = 0; i < 26; i++){
hash[order[i]-'a'] = i;
}
for(int i = 0; i < words.size()-1; i++){
bool res = isSorted(words[i], words[i+1]);
if(!res){
return false;
}
}
return true;
}
};
|
- 时间复杂度：需要遍历words中的每一个word，假设有n个，每个word平均长度为m，即O(mn)。
- 空间复杂度：O(1)。
分析
一天有24小时，即1440分钟。如果用一个长度为1440的数组表示一天的时间，那么数组下标为0的位置对应时间00：00，下标为1的位置对应时间00：01，以此类推，下标为1439的位置对应23：59。数组中的每个元素是true或false的标识，表示对应的时间是否存在于输入的时间数组中。
有了这个辅助数组，就只需要从头到尾扫描一遍，相邻的两个为true的值表示对应的两个时间在输入时间数组中是相邻的。例如，输入时间数组[“23：50”，”23：59”，”00：00”]，数组中只有下标为0、1430和1439这3个位置的值为true，其他位置的值都是false。
由于数组的下标对应的是时间，因此两个时间之间的时间差就是它们在数组中对应的下标之差。23：50和23：59之间相隔9分钟，它们在数组中的下标之差也是9。
其实，这个数组模拟了一个键为时间、值为true或false的哈希表。可以用数组模拟哈希表的原因是一天的分钟数是已知的，而且数组的长度为1440，也不算太长。有了这个数组，就可以和用哈希表一样，在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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public:
int getMinutes(string s){
return ((s[0] - '0') * 10 + (s[1] - '0')) * 60 + (s[3] - '0') * 10 + (s[4] - '0');
}
int findMinDifference(vector<string>& timePoints) {
bool time[1440] = {false};
for(int i = 0; i < timePoints.size(); i++){
int index = getMinutes(timePoints[i]);
if(time[index]){
return 0;
}
time[index] = true;
}
int res = INT_MAX;
int pre = -1;
int firstTime = -1;
for(int i = 0; i < 1440; i++){
if(time[i]){
if(pre != -1){
res = min(res, i - pre);
}
if(firstTime == -1) firstTime = i;
pre = i;
}
}
res = min(res, 1440 - pre + firstTime);
return res;
}
};
|
- 时间复杂度：在记录时间点的循环中，我们遍历了输入数组 timePoints，其时间复杂度为 O(n)，其中 n 是时间点的数量。在遍历辅助数组 time 来计算最小时间差时，我们遍历了一次长度为 1440 的数组，其时间复杂度为 O(1440) = O(1)。因此，总的时间复杂度为 O(n)。
- 空间复杂度：使用了一个大小为 1440 的辅助数组 time 来记录时间点的出现情况，因此空间复杂度为 O(1)。
总结
本章介绍了哈希表。哈希表的时间效率很高，添加、删除和查找操作的时间复杂度都是O（1）。
为了设计一个哈希表，首先需要一个数组，把每个键的哈希值映射到数组的一个位置。为了解决冲突，可以把映射到同一位置的多个键用链表存储。同时，为了避免链表太长，当哈希表中元素的数目与数组的长度的比值超过一定的阈值时，则增加数组的长度并根据新的长度重新映射每个键的位置。
如果结合哈希表和其他数据结构的特点，则还可以设计出很多更加高级、更加复杂的数据结构，如最近最少使用缓存。
在解决算法面试题时，哈希表是经常被使用的工具，用来记录字符串中字母出现的次数、字符串中字符出现的位置等信息。
如果哈希表的键的数目是固定的，并且数目不太大，那么也可以用数组来模拟哈希表，数组的下标对应哈希表的键，而数组的值与哈希表的值对应。