题目:
不使用任何内建的哈希表库设计一个哈希集合(HashSet)。
实现 MyHashSet
类:
-
void add(key)
向哈希集合中插入值key
。 -
bool contains(key)
返回哈希集合中是否存在这个值key
。 -
void remove(key)
将给定值key
从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。
提示:
0 <= key <= 10^6
- 最多调用
104
次add
、remove
和contains
思考:
偷懒做法:超大数组
因为 0<= key <= 10^6,所以可以建立一个长度为 10^6 + 1 的超大数组,数组的索引代表key值,数组的值(True / False)代表是否存在key值。代码如下:
class MyHashSet(object):
def __init__(self):
self.hashset = [False] * 1000001
def add(self, key):
"""
:type key: int
:rtype: None
"""
self.hashset[key] = True
def remove(self, key):
"""
:type key: int
:rtype: None
"""
self.hashset[key] = False
def contains(self, key):
"""
:type key: int
:rtype: bool
"""
return self.hashset[key]
提交通过:
正经做法:哈希函数+链地址法
设置一个长度为volume的数组hash,由volume个空列表组成。哈希函数为index=key%volume。那么对于任意值key,用哈希函数计算得到key所在的列表的位置,然后在列表中进行add、remove、contains操作。
由于 0<= key <= 10^6,所以取volume值为10^3,代码如下:
class MyHashSet(object):
def __init__(self):
self.volume = 1000
self.hashset = [[] for _ in range(self.volume)]
def _hash(self, key):
return key % self.volume # 哈希函数
def add(self, key):
"""
:type key: int
:rtype: None
"""
index = self._hash(key)
if key not in self.hashset[index]:
self.hashset[index].append(key)
def remove(self, key):
"""
:type key: int
:rtype: None
"""
index = self._hash(key)
if key in self.hashset[index]:
self.hashset[index].remove(key)
def contains(self, key):
"""
:type key: int
:rtype: bool
"""
index = self._hash(key)
if key in self.hashset[index]:
return True
return False
提交通过:
文章来源:https://www.toymoban.com/news/detail-851929.html
文章来源地址https://www.toymoban.com/news/detail-851929.html
到了这里,关于初学python记录:力扣705. 设计哈希集合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!