leetcode 432 全 O(1) 的數據結構,設計數據結構

實現一個數據結構支持以下操作:

  1. Inc(key) - 插入一個新的值為 1 的 key。或者使一個存在的 key 增加一,保證 key 不為空字符串。
  2. Dec(key) - 如果這個 key 的值是 1,那麼把他從數據結構中移除掉。否者使一個存在的 key 值減一。如果這個 key 不存在,這個函數不做任何事情。key 保證不為空字符串。
  3. GetMaxKey() - 返回 key 中值最大的任意一個。如果沒有元素存在,返回一個空字符串""。
  4. GetMinKey() - 返回 key 中值最小的任意一個。如果沒有元素存在,返回一個空字符串""。

挑戰:以 O(1) 的時間複雜度實現所有操作。

思路是,我們建立一個次數分層的結構,次數多的在頂層,每一層放相同次數的key值,例如下面這個例子:

"A": 4, "B": 4, "C": 2, "D": 1

那麼用我們設計的結構保存出來就是:

row0: val = 4, keys = {"A", "B"}

row1: val = 2, keys = {"C"}

row2: val = 1, keys = {"D"}

leetcode 432 全 O(1) 的數據結構,設計數據結構

leetcode 432 全 O(1) 的數據結構,設計數據結構

leetcode 432 全 O(1) 的數據結構,設計數據結構


分享到:


相關文章: