首先，我们看一道题目，用此题目为例说明，使用数组代替哈希表的使用
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例:
s = “abaccdeff”
返回 “b”
s = "”
返回 " "
限制：
0 <= s 的长度 <= 50000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解 :
思路一 ：
- 使用 HashMap
- 遍历字符串, map中存储 <字符 ：index>
- 遍历过程中，如果 map 中包含 当前字符，则 map.put(当前字符 : -1)
- 如果map中不包含当前字符， 则map.put(当前字符 : i)
- 字符串遍历完毕
- map中保存的就是：
- 重复字符对应的value为 -1
- 不重复字符对应的 value 就是其下标
- 再次遍历一遍字符串
- map中取出，当前字符对应的 value, value不为 -1 时， 为最终结果
- 遍历完毕，如果没有找到 value 不为 -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
|
/**
*
* 利用 HashMap
* 遍历字符串, map中存储 <字符 : index>
* 遍历过程中，如果 map 中包含 当前字符， 则 map.put(当前字符 : -1),-1表示有重复不符合要求
* 如果 map 中不包含 当前字符， 则 map.put(当前字符 : i)
*
* 字符串遍历完毕
* map中保存的就是
* 重复字符对应的 value 是 -1， 不重复字符对应的value 为 下标
*
* 两种方法
* 一，遍历 字符串，遍历的字符 在 map中对应的value不为 -1时。 则为最终结果
* 遍历完毕，如果没有找到value不为 -1的。 则返回 ' '
*
* 二，要么 遍历 map
* 记录，不为 -1的，所有value中的最小值，即为最终结果的下标
*
* */
public static char firstUniqChar(String s) {
HashMap<Character, Integer> map = new HashMap<>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (map.containsKey(chars[i])){
map.put(chars[i], -1);
}else {
map.put(chars[i], i);
}
}
for (int i = 0; i < chars.length; i++) {
if (map.get(chars[i]) != -1) return chars[i];
}
return ' ';
}
|
复杂度分析
时间复杂度 O(N) 遍历了两遍字符串
空间复杂度 O(N) 使用了额外的哈希表内存空间
思路二 ：
- 跟思路一方法一样， 优化的地方在于
- 因为 此题目中，字符串长度 0 <= s 的长度 <= 50000， 而 字符串中均为小写字母。
- 所以，遍历 一遍哈希表，取出 value 不为 -1的最小的值，key即为最终结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public static char firstUniqChar(String s) {
HashMap<Character, Integer> map = new HashMap<>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (map.containsKey(chars[i])){
map.put(chars[i], -1);
}else {
map.put(chars[i], i);
}
}
Object[] objs = map.keySet().toArray();
int resIdx = Integer.MAX_VALUE;
for (int i = 0; i < objs.length; i++) {
if (map.get(objs[i]) == -1) continue;
resIdx = Math.min(resIdx, map.get(objs[i]));
}
return resIdx == Integer.MAX_VALUE ? ' ' : chars[resIdx];
}
|
复杂度分析 :
- 时间复杂度 : O(N),
- 思路一中，也是O(N), 但是我们方法二中，省去了一遍遍历。第二遍遍历哈希表，因为都是 小写字母，所以map中最多 26 个键值对，第二次遍历是常数级别的时间复杂度.
- 时间复杂度 : O(N)
- 和思路一一样，使用了额外的哈希表，时间复杂度为 O(N)
思路三: 数组代替哈希表
思路三是咱们今天要解决的重点, 用数组代替哈希表来提高效率
- 通常这种情况，适用在 哈希表的 key 数量有限，且有序
- 比如 只包含 小写字母， 或者是 key 是char类型的等等的情况
- 比如今天这道题目，题目中明确说明了，字符串中的字符均为小写字母
- 而小写字母一共只有26个，所以我们可以利用一个长度为 26的数组来代替哈希表进行存储
- 数组即支持随机访问，也没有哈希表底层那么复杂的数据结构
- 所以操作上会快一些。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
/**
*
* 优化
* 因为 s只包含小写字符
* 所以可以使用数组, 代替哈希表
*
* */
public static char firstUniqChar1(String s) {
char[] chars = s.toCharArray();
int[] nums = new int[26];
for (int i = 0; i < chars.length; i++) {
nums[chars[i] - 'a'] ++;
}
for (int i = 0; i < chars.length; i++) {
if (nums[chars[i] - 'a'] == 1) return chars[i];
}
return ' ';
}
|
复杂度分析 :
- 从上图可以看出，在执行耗时上有了明显的提高。
- 由此可证明，使用数组，代替哈希表确实使得效率提高了很多。
- 时间复杂度 : O(N)
- 空间复杂度 : O(N)