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

閱讀時間約 4 分鐘
raw-image

這題的題目在這裡:

題目敘述

題目會給定一組已經規定好的介面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 <= 106
  • At most 104 calls will be made to addremove, 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

85會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
題目會給我們兩條已經從小到大排序好的串列,要求我們依照從小到大的順序,合併這兩條串列。
題目會給定一組輸入陣列,裡面每個參數分別代表矩陣的寬和高。 如果有兩個矩陣的寬/高的比例是相同的,代表這兩個矩陣是等比例的。 要求我們計算,等比例的矩陣pair總共有多少個?
題目會給定我們一個輸入陣列,要求我們計算好配對的數目有多少個? 好配對的定義: 兩個數字相同,但是陣列索引一個在前,一個在後。 nums[i] == nums[j] and i < j. 這樣 (i, j) 就稱為一組好配對。
題目會給定我們一個陣列和參數k,要求我們將陣列右旋k次,然後輸出內容。 例如[1,2,3,4,5] 右旋 2次,輸出就是[4,5,1,2,3]
題目會給定我們一個陣列,要求我們找出裡面統計最多出現次數的偶數 。 假如有兩個偶數出現的次數一樣多,取最數字比較小的那個最為答案。
題目會給定我們一個陣列,陣列長度為n。 要求我們找出裡面出現次數超過 n / 3次的數字。
題目會給我們兩條已經從小到大排序好的串列,要求我們依照從小到大的順序,合併這兩條串列。
題目會給定一組輸入陣列,裡面每個參數分別代表矩陣的寬和高。 如果有兩個矩陣的寬/高的比例是相同的,代表這兩個矩陣是等比例的。 要求我們計算,等比例的矩陣pair總共有多少個?
題目會給定我們一個輸入陣列,要求我們計算好配對的數目有多少個? 好配對的定義: 兩個數字相同,但是陣列索引一個在前,一個在後。 nums[i] == nums[j] and i < j. 這樣 (i, j) 就稱為一組好配對。
題目會給定我們一個陣列和參數k,要求我們將陣列右旋k次,然後輸出內容。 例如[1,2,3,4,5] 右旋 2次,輸出就是[4,5,1,2,3]
題目會給定我們一個陣列,要求我們找出裡面統計最多出現次數的偶數 。 假如有兩個偶數出現的次數一樣多,取最數字比較小的那個最為答案。
題目會給定我們一個陣列,陣列長度為n。 要求我們找出裡面出現次數超過 n / 3次的數字。
你可能也想看
Google News 追蹤
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
本篇文章介紹如何使用PyTorch構建和訓練圖神經網絡(GNN),並使用Cora資料集進行節點分類任務。通過模型架構的逐步優化,包括引入批量標準化和獨立的消息傳遞層,調整Dropout和聚合函數,顯著提高了模型的分類準確率。實驗結果表明,經過優化的GNN模型在處理圖結構數據具有強大的性能和應用潛力。
Thumbnail
如果對於無邊無際的海洋非常憧憬的朋友們,那今天介紹的沖繩五日跟團一定會非常適合你。這個日本旅遊團運用五天的時間帶領大家到萬座毛、美國村和知念岬公園感受湛藍海洋的魅力,對於美食講究的朋友,這裡也有豐富的美食吃到飽,絕對不會讓你在旅程中餓到肚子。和AsiaYo一起出發認識這條夢幻的日本跟團路線吧!
Thumbnail
只有九張椅子的十人座餐桌,「忍冬」花紋的地毯,「龍膽」圖案的玻璃,「彩夏」的畫作——寂靜的宅邸裡,許多物品和劇團成員的姓名間竟有著詭異的巧合,掛在大廳中央的油畫,已逝的女主人 白須賀夫人更是與女演員 深月長得一模一樣? 眾人陷入謎團之際,連續殺人案也悄悄於這座籠罩在白雪與暗夜間的舞臺拉開序幕。
Thumbnail
工作佔了我們每天多數時間,很多人會感嘆做自己熱情與目標的時間不夠,加上長期工作下來,體力早已不支倒地,只能躺平休息(?)。亞馬遜作為一間工作多、餐廳要錢,員工福利只有吃不完的香蕉的大公司,真的可以做到 1 小時做完 1 天工作嗎?
Thumbnail
題目會給定一組已經規定好的介面interface,要求我們實作HashSet這種資料結構。也就是一般數學和程式語言中所說的"集合"。
Thumbnail
今天台股大跌兩百多點 走勢再度回測頸線支撐 究竟會不會守得住呢!? 沒人可以知道!!! 只能做好該做的準備,來面對之後會出現的狀況!!! 大跌走勢之下,你要做什麼!? 個人經驗分享!!!
Thumbnail
我一直很喜歡林明子的作品,總能依著孩子的成長經驗,描繪出孩子純真又樸實的姿態神情,色調繽紛又帶點柔和,營造出童年的幸福溫馨感。 我跟小貝之前就收藏了《第一次上街買東西》、《今天是什麼日子》、《妹妹住院了》、《圓圓的野餐》,大約在小貝2-3歲時,我們很常共讀這幾本,那時想要長大的小貝很常問他何時可以跟
Thumbnail
後面會再一篇介紹有去試戴過的,比較高單的婚戒品牌,敬請期待!!! 最後我們選購的是『Chaumet尚美』頂級珠寶工藝,皇室御用。過程中~平價與高價品牌穿插預約鑑賞,Chaumet佩戴手感完勝,順手不卡卡,所以選購此品牌。 本文小鑽戒0.18-0.5分以下,大鑽戒0.5起,0.5分(車工好)視覺就很好
Thumbnail
13年的等待其實還蠻值得的。 本片適合找imax3d觀賞,會有很棒的觀影體驗。 如果想要互動效果,可選擇4dx影廳,不過這次的主軸是水,觀賞體驗會很有感。 電影本身延續阿凡達第一集的設定,故事也和第一集的風格類似,基本上會有似曾相識的劇情安排,但整體故事大致上沒有太多缺陷,可以順順的看完。
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
本篇文章介紹如何使用PyTorch構建和訓練圖神經網絡(GNN),並使用Cora資料集進行節點分類任務。通過模型架構的逐步優化,包括引入批量標準化和獨立的消息傳遞層,調整Dropout和聚合函數,顯著提高了模型的分類準確率。實驗結果表明,經過優化的GNN模型在處理圖結構數據具有強大的性能和應用潛力。
Thumbnail
如果對於無邊無際的海洋非常憧憬的朋友們,那今天介紹的沖繩五日跟團一定會非常適合你。這個日本旅遊團運用五天的時間帶領大家到萬座毛、美國村和知念岬公園感受湛藍海洋的魅力,對於美食講究的朋友,這裡也有豐富的美食吃到飽,絕對不會讓你在旅程中餓到肚子。和AsiaYo一起出發認識這條夢幻的日本跟團路線吧!
Thumbnail
只有九張椅子的十人座餐桌,「忍冬」花紋的地毯,「龍膽」圖案的玻璃,「彩夏」的畫作——寂靜的宅邸裡,許多物品和劇團成員的姓名間竟有著詭異的巧合,掛在大廳中央的油畫,已逝的女主人 白須賀夫人更是與女演員 深月長得一模一樣? 眾人陷入謎團之際,連續殺人案也悄悄於這座籠罩在白雪與暗夜間的舞臺拉開序幕。
Thumbnail
工作佔了我們每天多數時間,很多人會感嘆做自己熱情與目標的時間不夠,加上長期工作下來,體力早已不支倒地,只能躺平休息(?)。亞馬遜作為一間工作多、餐廳要錢,員工福利只有吃不完的香蕉的大公司,真的可以做到 1 小時做完 1 天工作嗎?
Thumbnail
題目會給定一組已經規定好的介面interface,要求我們實作HashSet這種資料結構。也就是一般數學和程式語言中所說的"集合"。
Thumbnail
今天台股大跌兩百多點 走勢再度回測頸線支撐 究竟會不會守得住呢!? 沒人可以知道!!! 只能做好該做的準備,來面對之後會出現的狀況!!! 大跌走勢之下,你要做什麼!? 個人經驗分享!!!
Thumbnail
我一直很喜歡林明子的作品,總能依著孩子的成長經驗,描繪出孩子純真又樸實的姿態神情,色調繽紛又帶點柔和,營造出童年的幸福溫馨感。 我跟小貝之前就收藏了《第一次上街買東西》、《今天是什麼日子》、《妹妹住院了》、《圓圓的野餐》,大約在小貝2-3歲時,我們很常共讀這幾本,那時想要長大的小貝很常問他何時可以跟
Thumbnail
後面會再一篇介紹有去試戴過的,比較高單的婚戒品牌,敬請期待!!! 最後我們選購的是『Chaumet尚美』頂級珠寶工藝,皇室御用。過程中~平價與高價品牌穿插預約鑑賞,Chaumet佩戴手感完勝,順手不卡卡,所以選購此品牌。 本文小鑽戒0.18-0.5分以下,大鑽戒0.5起,0.5分(車工好)視覺就很好
Thumbnail
13年的等待其實還蠻值得的。 本片適合找imax3d觀賞,會有很棒的觀影體驗。 如果想要互動效果,可選擇4dx影廳,不過這次的主軸是水,觀賞體驗會很有感。 電影本身延續阿凡達第一集的設定,故事也和第一集的風格類似,基本上會有似曾相識的劇情安排,但整體故事大致上沒有太多缺陷,可以順順的看完。