前往
大廳
主題

LeetCode - 705. Design HashSet 解題心得

Not In My Back Yard | 2020-12-28 00:00:02 | 巴幣 0 | 人氣 433

題目連結:


題目意譯:
設計一個雜湊集合 HashSet,但是不得使用任何內建的雜湊表函式庫等。

特定地,你需要包含以下函式:
add(value): 插入一個值到 HashSet 裡。
contains(value): 回傳 value 是否存在於 HashSet。
remove(value): 從 HashSet 移除 value 這個值。如果 value 並不存在於 HashSet 中,則不需做任何動作。

注:
所有的值皆位於 [0, 1000000] 範圍之中。
操作數量一定位於 [1, 10000] 範圍之中。
請不要使用任何內建雜湊函式庫。



範例測資:
MyHashSet hashSet = new MyHashSet();
hashSet.add(1);         
hashSet.add(2);         
hashSet.contains(1);    // 回傳真(true)
hashSet.contains(3);    // 回傳假(false)(找不到)
hashSet.add(2);          
hashSet.contains(2);    // 回傳真
hashSet.remove(2);          
hashSet.contains(2);    // 回傳假(已經移除)


解題思維:
如果不考慮空間消耗的話,就直接開一個大小為 1000001 的布林陣列,什麼值進來就將對應索引值的位置設為真(True)代表有這個數字、要刪除什麼值就直接將對應位置設為假(False)、要找值就直接看對應的布林陣列之位置之值。

但是如果想要省空間的話,可以使用類似這題的方式——將進來的數字取除以某個數字 M 的餘數,而上述的陣列變為儲存連結串列(Linked List)的開頭或是一棵平衡二元樹,端看讀者想實作何者。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作