經典實作題 Design HashSet 實作集合 Leetcode #705

這題的題目在這裡:

題目敘述

題目會給定一組已經規定好的介面interface，要求我們實作HashSet這種資料結構。也就是一般數學和程式語言中所說的"集合"。

測試範例

Input
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]

Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // return False, (already removed)

約束條件

Constraints:

• 0 <= key <= 106
• At most 104 calls will be made to add, remove, and contains.

演算法

集合最重要的就是 存在性 的檢查，每個成員的存在可以用一個bit的True/False來代表 在集合內/不在集合內。

若是新增 add()，就把對應的bit flag舉起來，設定成1

若是移除 remove()，就把對應的bit flag清除，清成0

若是檢查成員是否存在contains()，就把對應的bit flag和bit mask做 bitwise AND ，若結果non-zero則代表存在；反之，則不存在。

程式碼

class MyHashSet:

　def __init__(self):
　　
　　# initialize hashpool with 0b 0000000...0
　　self.hashpool = 0;

　def add(self, key: int) -> None:
　　
　　# raise corresponding bit flag for k
　　self.hashpool |= (1<<key)
　　return 
　
　def remove(self, key: int) -> None:
　　
　　# clear corresponding bit flag for k
　　self.hashpool &= ~(1<<key)　
		return

　def contains(self, key: int) -> bool:
　　
　　# check corresponding bit flag for k
　　return self.hashpool & (1<<key)

複雜度分析

時間複雜度:

O(1) add, remove, contains 皆在常數時間O(1)內可以完成。

空間複雜度:

O(n) = O( max integer of input ) = O( 最大的輸入整數key值)

因為一個數字背後需要一個對應的bit flag來代表存在與否。

關鍵知識點

想到set集合最關鍵的就是 存在/不存在 的檢查，二元檢查剛好可以對應到bit flag的True/False，想到用bit flag和二進位操作的方式來實作set

Reference:

[1] Python by bytearray//bit-manipulation//bit-hack [ w/Explanation] - Design HashSet - LeetCode