LeetCode 705：設計哈希集合 Design HashSet
- 2019 年 10 月 7 日
- 筆記
題目：
不使用任何內建的哈希表庫設計一個哈希集合
具體地說，你的設計應該包含以下的功能
add(value)：向哈希集合中插入一個值。contains(value)：返回哈希集合中是否存在這個值。remove(value)：將給定值從哈希集合中刪除。如果哈希集合中沒有這個值，什麼也不做。
Design a HashSet without using any built-in hash table libraries.
To be specific, your design should include these functions:
add(value): Insert a value into the HashSet.contains(value): Return whether the value exists in the HashSet or not.remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.
示例:
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 (已經被刪除)
注意：
- 所有的值都在
[1, 1000000]的範圍內。 - 操作的總數目在
[1, 10000]範圍內。 - 不要使用內建的哈希集合庫。
Note:
- All values will be in the range of
[0, 1000000]. - The number of operations will be in the range of
[1, 10000]. - Please do not use the built-in HashSet library.
解題思路：
題目明確限定了數據大小和數據集大小，都在int整型範圍內，所以最簡單的解法就是，以一個長度為10000001的布爾類型 數組，索引位置就是數據值大小。True、False代表哈希集合內是否有該數。這應該是最簡單的哈希散列函數了：y = x
程式碼：
Java：
class MyHashSet { private boolean[] hashSet; /** * Initialize your data structure here. */ public MyHashSet() { this.hashSet = new boolean[10000001]; } public void add(int key) { hashSet[key] = true; } public void remove(int key) { hashSet[key] = false; } /** * Returns true if this set contains the specified element */ public boolean contains(int key) { return hashSet[key]; } }
Python：
class MyHashSet: def __init__(self): """ Initialize your data structure here. """ self.hash_set = [False]*1000001 def add(self, key: int) -> None: self.hash_set[key] = True def remove(self, key: int) -> None: self.hash_set[key] = False def contains(self, key: int) -> bool: """ Returns true if this set contains the specified element """ return self.hash_set[key]
