題目連結:
題目意譯:
設計一個資料結構,其可以維護存在於其中的數字之數值並回答一些關於這些數字的出現頻率之詢問(Query)。
實作類別 FrequencyTracker:
FrequencyTracker():初始化一個 FrequencyTracker 物件,其一開始含有著一個空陣列。
void add(int number):將 number 加到資料結構中。
void deleteOne(int number):將 number 在資料結構的出現次數減一。資料結構可能不包含 number,此時什麼變化都不會發生。
bool hasFrequency(int frequency):如果存在著某個數字出現 frequency 次,則回傳真(True);反之,回傳假(False)。
限制:
1 ≦ number ≦ 10 ^ 5
1 ≦ frequency ≦ 10 ^ 5
最多呼叫 add 、 deleteOne 和 hasFrequency 總計 2 × 10 ^ 5 次。
範例測資:
範例 1:
輸入
["FrequencyTracker", "add", "add", "hasFrequency"]
[[], [3], [3], [2]]
輸出
[null, null, null, true]
解釋
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.add(3); // 資料結構現在包含 [3]
frequencyTracker.add(3); // 資料結構現在包含 [3, 3]
frequencyTracker.hasFrequency(2); // 回傳真,因為 3 出現兩次
範例 2:
輸入
["FrequencyTracker", "add", "deleteOne", "hasFrequency"]
[[], [1], [1], [1]]
輸出
[null, null, null, false]
解釋
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.add(1); // 資料結構現在包含 [1]
frequencyTracker.deleteOne(1); // 資料結構變成空的
frequencyTracker.hasFrequency(1); // 回傳 false, 因為資料結構為空
範例 3:
輸入
["FrequencyTracker", "hasFrequency", "add", "hasFrequency"]
[[], [2], [3], [1]]
輸出
[null, false, null, true]
解釋
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.hasFrequency(2); // 回傳假,因為資料結構為空
frequencyTracker.add(3); // 資料結構現在包含 [3]
frequencyTracker.hasFrequency(1); // 回傳真,因為 3 出現 1 次
解題思維:
用兩個雜湊表(Hash Table),一個儲存每一種數字當前的出現次數(稱 C)以及每一種出現次數有多少數字符合(稱 F)來模擬即可。
每當呼叫 add 時,就是把 F[C[number]] 減去 1 、 F[C[number] + 1] 加上 1,然後再將 C[number] 加上 1;
每當呼叫 deleteOne 時,檢查 number 有無存在 C 裡(或是檢查 C[number] 是否為零)。如果不存在(或為零),則無視;反之則將 F[C[number]] 減去 1 、 F[C[number] - 1](如果 C[number] - 1 是 0,則可做也可不做),最後再將 C[number] 減去 1;
每當呼叫 hasFrequency 時,檢查 F[frequency] 之值是否大於等於 1 即可。如果是,則代表有數字出現 frequency 次;反之則無。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。