題目會給定一組已經規定好的介面interface,要求我們實作HashSet這種資料結構。也就是一般數學和程式語言中所說的"集合"。
Example 1:
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 <= 10
6
10
4
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