外贸网站建设 公司价格,hpsocket 网站开发,灯具网站模板,免费代理ip文章目录题目标题和出处难度题目描述要求示例数据范围解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析题目
标题和出处
标题#xff1a;设计哈希集合
出处#xff1a;705. 设计哈希集合
难度
3 级
题目描述
要求
不使用任何内建的哈希表库设计一个哈希…
文章目录题目标题和出处难度题目描述要求示例数据范围解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析题目
标题和出处
标题设计哈希集合
出处705. 设计哈希集合
难度
3 级
题目描述
要求
不使用任何内建的哈希表库设计一个哈希集合。
实现 MyHashSet\texttt{MyHashSet}MyHashSet 类
voidadd(key)\texttt{void add(key)}void add(key) 向哈希集合中插入值 key\texttt{key}key。boolcontains(key)\texttt{bool contains(key)}bool contains(key) 返回哈希集合中是否存在这个值 key\texttt{key}key。voidremove(key)\texttt{void remove(key)}void remove(key) 将给定值 key\texttt{key}key 从哈希集合中删除。如果哈希集合中没有这个值什么也不做。
示例
示例 1
输入 [MyHashSet,add,add,contains,contains,add,contains,remove,contains]\texttt{[MyHashSet, add, add, contains, contains, add, contains, remove, contains]}[MyHashSet, add, add, contains, contains, add, contains, remove, contains] [[],[1],[2],[1],[3],[2],[2],[2],[2]]\texttt{[[], [1], [2], [1], [3], [2], [2], [2], [2]]}[[], [1], [2], [1], [3], [2], [2], [2], [2]] 输出 [null,null,null,true,false,null,true,null,false]\texttt{[null, null, null, true, false, null, true, null, false]}[null, null, null, true, false, null, true, null, false] 解释 MyHashSetmyHashSetnewMyHashSet();\texttt{MyHashSet myHashSet new MyHashSet();}MyHashSet myHashSet new MyHashSet(); myHashSet.add(1);\texttt{myHashSet.add(1);}myHashSet.add(1); // set[1]\texttt{set [1]}set [1] myHashSet.add(2);\texttt{myHashSet.add(2);}myHashSet.add(2); // set[1,2]\texttt{set [1, 2]}set [1, 2] myHashSet.contains(1);\texttt{myHashSet.contains(1);}myHashSet.contains(1); // 返回 True\texttt{True}True myHashSet.contains(3);\texttt{myHashSet.contains(3);}myHashSet.contains(3); // 返回 False\texttt{False}False未找到 myHashSet.add(2);\texttt{myHashSet.add(2);}myHashSet.add(2); // set[1,2]\texttt{set [1, 2]}set [1, 2] myHashSet.contains(2);\texttt{myHashSet.contains(2);}myHashSet.contains(2); // 返回 True\texttt{True}True myHashSet.remove(2);\texttt{myHashSet.remove(2);}myHashSet.remove(2); // set[1]\texttt{set [1]}set [1] myHashSet.contains(2);\texttt{myHashSet.contains(2);}myHashSet.contains(2); // 返回 False\texttt{False}False已移除
数据范围
0≤key≤106\texttt{0} \le \texttt{key} \le \texttt{10}^\texttt{6}0≤key≤106最多调用 104\texttt{10}^\texttt{4}104 次 add\texttt{add}add、remove\texttt{remove}remove 和 contains\texttt{contains}contains
解法一
思路和算法
由于 key\textit{key}key 的取值范围是 [0,106][0, 10^6][0,106]因此可以创建长度为 106110^6 11061 的布尔型数组表示哈希集合数组中的下标为 key\textit{key}key 的元素值表示 key\textit{key}key 是否在哈希集合中。
构造方法中将数组初始化为长度 106110^6 11061 的数组并将数组中的全部元素初始化为 false\text{false}false。
对于 add\textit{add}add 操作将数组中的下标为 key\textit{key}key 的元素设为 true\text{true}true。
对于 contains\textit{contains}contains 操作返回数组中的下标为 key\textit{key}key 的元素。
对于 remove\textit{remove}remove 操作将数组中的下标为 key\textit{key}key 的元素设为 false\text{false}false。
需要说明的是该解法虽然实现简单但是不适合在面试中使用。
代码
class MyHashSet {boolean[] set;public MyHashSet() {set new boolean[1000001];Arrays.fill(set, false);}public void add(int key) {set[key] true;}public void remove(int key) {set[key] false;}public boolean contains(int key) {return set[key];}
}复杂度分析 时间复杂度构造方法的时间复杂度是 O(C)O(C)O(C)各项操作的时间复杂度都是 O(1)O(1)O(1)其中 CCC 是 key\textit{key}key 的取值范围的元素个数这道题中 C1061C 10^6 1C1061。 构造方法需要创建长度为 CCC 的数组并将每个元素设为初始值时间复杂度是 O(C)O(C)O(C)。 各项操作只需要对数组中的一个元素赋值或返回元素值时间复杂度是 O(1)O(1)O(1)。 空间复杂度O(C)O(C)O(C)其中 CCC 是 key\textit{key}key 的取值范围的元素个数这道题中 C1061C 10^6 1C1061。需要创建长度为 CCC 的数组表示哈希集合。
解法二
思路和算法
哈希集合的常见实现方法是链表数组数组的每个下标对应哈希函数可以映射到的索引当出现哈希冲突时使用链地址法解决哈希冲突。
用 BASE\textit{BASE}BASE 表示链表数组的长度则可以使用一个简单的哈希函数hash(x)xmodBASE\text{hash}(x) x \bmod \textit{BASE}hash(x)xmodBASE每个键经过哈希函数映射之后的值一定在范围 [0,BASE−1][0, \textit{BASE} - 1][0,BASE−1] 内。为了将哈希函数的值尽可能均匀分布降低哈希冲突的频率链表数组的长度应选择质数。此处取链表数组的长度为 101310131013。
构造方法中将链表数组初始化为长度 BASE\textit{BASE}BASE 的链表数组并将链表数组中的全部元素初始化为空链表。
对于各项操作首先计算 key\textit{key}key 对应的哈希值得到链表数组的下标根据下标在链表数组中得到相应的链表然后在链表中执行相应操作。
对于 add\textit{add}add 操作在链表数组中得到相应的链表之后遍历链表如果遇到元素 key\textit{key}key 则不执行任何操作直接返回如果遍历结束没有遇到元素 key\textit{key}key 则在链表末尾添加元素 key\textit{key}key。
对于 contains\textit{contains}contains 操作在链表数组中得到相应的链表之后遍历链表如果遇到元素 key\textit{key}key 则返回 true\text{true}true如果遍历结束没有遇到元素 key\textit{key}key 则返回 false\text{false}false。
对于 remove\textit{remove}remove 操作在链表数组中得到相应的链表之后遍历链表如果遇到元素 key\textit{key}key 则将其删除如果遍历结束没有遇到元素 key\textit{key}key 则不执行任何操作。
实现方面为了提升运行效率使用迭代器遍历链表和执行删除操作。
代码
class MyHashSet {private static final int BASE 1013;private LinkedListInteger[] set;public MyHashSet() {set new LinkedList[BASE];for (int i 0; i BASE; i) {set[i] new LinkedListInteger();}}public void add(int key) {int index key % BASE;LinkedListInteger list set[index];IteratorInteger iterator list.iterator();while (iterator.hasNext()) {Integer element iterator.next();if (element key) {return;}}list.offerLast(key);}public void remove(int key) {int index key % BASE;LinkedListInteger list set[index];IteratorInteger iterator list.iterator();while (iterator.hasNext()) {Integer element iterator.next();if (element key) {iterator.remove();break;}}}public boolean contains(int key) {int index key % BASE;LinkedListInteger list set[index];IteratorInteger iterator list.iterator();while (iterator.hasNext()) {Integer element iterator.next();if (element key) {return true;}}return false;}
}复杂度分析 时间复杂度构造方法的时间复杂度是 O(BASE)O(\textit{BASE})O(BASE)各项操作的时间复杂度都是 O(nBASE)O\Big(\dfrac{n}{\textit{BASE}}\Big)O(BASEn)其中 nnn 是哈希集合中的元素个数BASE\textit{BASE}BASE 是链表数组的长度。 构造方法需要创建长度为 BASE\textit{BASE}BASE 的数组并将每个元素设为初始值时间复杂度是 O(BASE)O(\textit{BASE})O(BASE)。 各项操作需要根据哈希函数计算哈希值然后遍历链表。计算哈希值需要 O(1)O(1)O(1) 的时间假设哈希值分布均匀每个链表的平均长度是 O(nBASE)O\Big(\dfrac{n}{\textit{BASE}}\Big)O(BASEn)因此需要 O(nBASE)O\Big(\dfrac{n}{\textit{BASE}}\Big)O(BASEn) 的时间遍历哈希表。 空间复杂度O(nBASE)O(n \textit{BASE})O(nBASE)其中 nnn 是哈希集合中的元素个数BASE\textit{BASE}BASE 是链表数组的长度。存储 nnn 个元素需要 O(n)O(n)O(n) 的空间链表数组需要 O(BASE)O(\textit{BASE})O(BASE) 的空间。
