原题
不使用任何内建的哈希表库设计一个哈希集合
具体地说,你的设计应该包含以下的功能
add(value)
:向哈希集合中插入一个值。contains(value)
:返回哈希集合中是否存在这个值。remove(value)
:将给定值从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。
示例:
MyHashSet hashSet = new MyHashSet();
hashSet.add(1);
hashSet.add(2);
hashSet.contains(1); // 返回 true
hashSet.contains(3); // 返回 false (未找到)
hashSet.add(2);
hashSet.contains(2); // 返回 true
hashSet.remove(2);
hashSet.contains(2); // 返回 false (已经被删除)
注意:
- 所有的值都在
[0, 1000000]
的范围内。 - 操作的总数目在
[1, 10000]
范围内。 - 不要使用内建的哈希集合库。
解法
思想
偷懒,已知值的范围,直接将整数值映射为哈希值,有多少个哈希值建多少个桶,用空间换时间。
代码
class MyHashSet {
boolean[] exist;
/** Initialize your data structure here. */
public MyHashSet() {
exist = new boolean[1000001];
}
public void add(int key) {
exist[key] = true;
}
public void remove(int key) {
exist[key] = false;
}
/** Returns true if this set contains the specified element */
public boolean contains(int key) {
return exist[key];
}
}
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet obj = new MyHashSet();
* obj.add(key);
* obj.remove(key);
* boolean param_3 = obj.contains(key);
*/
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode705-%e8%ae%be%e8%ae%a1%e5%93%88%e5%b8%8c%e9%9b%86%e5%90%88/