leetcode705-设计哈希集合

原题

不使用任何内建的哈希表库设计一个哈希集合

具体地说,你的设计应该包含以下的功能

  • 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/

发表回复

登录后才能评论