Go語言題解LeetCode705設計哈希集合
題目描述
705. 設計哈希集合
不使用任何內建的哈希表庫設計一個哈希集合(HashSet)。
實現 MyHashSet 類:
- void add(key) 向哈希集合中插入值 key 。
- bool contains(key) 返回哈希集合中是否存在這個值 key 。
- void remove(key) 將給定值 key 從哈希集合中刪除。如果哈希集合中沒有這個值,什麼也不做。 示例:
輸入: ["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"] [[], [1], [2], [1], [3], [2], [2], [2], [2]] 輸出: [null, null, null, true, false, null, true, null, false] 解釋: MyHashSet myHashSet = new MyHashSet(); myHashSet.add(1); // set = [1] myHashSet.add(2); // set = [1, 2] myHashSet.contains(1); // 返回 True myHashSet.contains(3); // 返回 False ,(未找到) myHashSet.add(2); // set = [1, 2] myHashSet.contains(2); // 返回 True myHashSet.remove(2); // set = [1] myHashSet.contains(2); // 返回 False ,(已移除)
提示:
- 0 <= key <= 10^6
- 最多調用 10^4 次 add、remove 和 contains
思路分析
實現使用瞭鏈地址法,解決哈希沖突方法使用瞭模取餘的方法(較簡單的)。
這裡說下為什麼大傢說模最好取質數,我的理解是取質數可以讓取餘後的結果更加均勻,以減少沖突。
舉個例子,假如我們取4為模,那麼雖然理論上我們應該會讓數字均勻落入4個桶中,但是對於下邊這個數組:
1,3,5,7,9
所有數字都落入瞭1,3兩個桶中,造成瞭極大的不均,導致哈希沖突發生頻繁。對於一個合數,隻要我們構造合數倍數相關的數組,就很容易使哈希沖突變多,所以盡量選用質數。
AC 代碼
struct Listnode{ int val; Listnode* next = nullptr; Listnode()=default; Listnode(int val){ this->val = val; } }; class MyHashSet { public: /** Initialize your data structure here. */ const int prime = 991; vector<Listnode*> nodes; MyHashSet(): nodes(prime, nullptr){ } void add(int key) { if(nodes[key%prime] == nullptr){ nodes[key%prime] = new Listnode(key); }else{ Listnode* node = nodes[key%prime]; while(node != nullptr){ if(node->val == key)return; node = node->next; } node = new Listnode(key); node->next = nodes[key%prime]; nodes[key%prime] = node; } } void remove(int key) { Listnode* prenode = nodes[key%prime]; if(prenode != nullptr && prenode->val == key){ if(prenode->next != nullptr){ nodes[key%prime] = prenode->next; delete prenode; }else{ delete prenode; nodes[key%prime] = nullptr; } return; } while(prenode != nullptr && prenode->next != nullptr){ if(prenode->next->val == key){ Listnode* temp = prenode->next; prenode->next = prenode->next->next; delete temp; return; } prenode = prenode->next; } } /** Returns true if this set contains the specif ied element */ bool contains(int key) { Listnode* node = nodes[key%prime]; while(node != nullptr){ if(node->val == key)return true; node = node->next; } 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); */
以上就是Go語言題解LeetCode705設計哈希集合的詳細內容,更多關於Go語言設計哈希集合的資料請關註WalkonNet其它相關文章!
推薦閱讀:
- 帶你粗略瞭解C++回文鏈表
- C語言詳細分析貪心策略中最小生成樹的Prime算法設計與實現
- 深入瞭解C++智能指針的使用
- C++數據結構之二叉搜索樹的實現詳解
- C++實現LeetCode(25.每k個一組翻轉鏈表)