每日一题705 hashset的实现

705. 设计哈希集合

实现 MyHashSet 类:

void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。

思路1

  • 直接使用的c++的内置函数 unordered_set 实现的( set 也可以)
  • 直接调用set的相关函数

    • find(key) 判断是否有key元素
    • erase(it) 移除it指向的元素
    • insert(key) 插入关键字为key的元素
class MyHashSet {
public:
    /** Initialize your data structure here. */
    set<int> us;//内部是红黑树

    MyHashSet() {

    }
    
    void add(int key) {
        us.insert(key);
    }
    
    void remove(int key) {
        auto it = us.find(key);
        if (it != us.end()) {
            us.erase(it);
        } 
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        if (us.find(key) != us.end()) {
            return true;
        } else {
            return false;
        }
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

思路2

  • 使用超大数组
  • 0 <= key <= 10^6 只要数组长度>10^6,就可以实现o(1)的添加、删除时间复杂度
  • 但是空间复杂度太高了
class MyHashSet {
public:
    /** Initialize your data structure here. */
    vector<int> res;
    MyHashSet() {
        res.resize(1000001);
    }
    
    void add(int key) {
        res[key] = 1;
    }
    
    void remove(int key) {
        res[key] = 0;
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        return res[key] == 0 ? false : true;
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

思路3

  • 拉链法减少冲突
  • 使用map,key为元素哈希之后的下标,value为实际key,用set存储(防止重复元素)
class MyHashSet {
public:
    /** Initialize your data structure here. */
    map<int, set<int>> res;
    MyHashSet() {
    }

    int hash(int key) {
        return key % 1009;
    }
    
    void add(int key) {
        int t = hash(key);
        res[t].insert(key);
    }
    
    void remove(int key) {
        int t = hash(key);
        if (res[t].count(key) == 0) {
            return;
        } else {
            res[t].erase(key);
        }
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        int t = hash(key);
        if (res[t].count(key) == 0) {
            return false;
        } else {
            return true;
        }
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

set的介绍

  1. set内部数据结构是红黑树,作为一种关联容器,按照关键字进行查找
  2. set的每个元素都是有序排列的
  3. set的元素值唯一,不允许有重复元素

unordered_set的介绍

  1. unordered_set 采用数据结构是哈希表
  2. 元素无序排列
  3. 关键字唯一

评论

暂无评论