LeetCode 哈希表 380. 常數時間插入、刪除和獲取隨機元素（設計數據結構 List HashMap底層 時間複雜度）

 

 

比起之前那些問計數哈希表的題目，這道題好像更接近哈希表的底層機制。

java中hashmap的實現是通過List<Node>,即鏈表的list，如果鏈表過長則換為紅黑樹，如果容量不足（裝填因子下）則擴充數組容量。解決衝突的方式是直接接在對應位置的鏈表上。

首先看看哈希表幾個操作的時間複雜度：

HashMap的新增：

  1. 計算key的哈希值
  2. 哈希值作為index，找到對應的數組位置
  3. 如果數組位置為空，直接存入
  4. 如果數組位置不為空，遍歷該鏈表，插入末尾

這裡考慮理想情況（無衝突），時間複雜度為O1

HashMap的刪除，查詢都是一樣的理解，如果沒得衝突，都是O1的複雜度。

如果衝突，可能出現On情況（鏈表），Ologn情況（紅黑樹）

 

返回隨機元素，這個則不好實現，因為HashMap是無序的，又沒得類似List那樣的索引，很難返回一個random的值。

接著考慮的一個方式就是，能不能把HashMap的key以0，1。。。的方式存到一個數組中，用random得到一個隨機的序號，然後在通過序號去找。

然而這裡犯了一個錯誤。這樣的方式其實無疑與把這個HashMap變成了一個LIst。當然插入是O1，但是刪除則不好操作了。

 

第二個想法是Hashset，但問題其實也一樣，這是一個無序的set，沒辦法搞random。這裡的無序set指的是插入進去之後放到的位置就是hash算出來的位置，顯然無法用隨機的方式使得每一個元素返回的概率相同。

 

第三個想法則是List作為基礎，再用HashMap來補缺陷。

LIst的操作複雜度：

  • append，直接在尾端加，O1
  • pop，直接去掉尾端，O1
  • 特定位置插入/刪除，都需要蘿蔔挪坑，On
  • 訪問特定位置元素，索引直接訪問，O1
  • 查，要跑一遍整個數組，On

所以Random很好做到，其餘的需要用append和pop搞事

append需要去重，我們把索引和值分別存入HashMap作為輔助

這樣要插入時，先用HashMap判斷有無（O1），然後直接插尾端（O1）

刪除稍麻煩一些，我們如果直接刪除真正位置，則需要挪位置變為On

所以用HashMap找到位置後，將該位置和List末尾做交換，然後PoP，這樣就是O1了。

 

class RandomizedSet {
  Map<Integer, Integer> dict;
  List<Integer> list;
  Random rand = new Random();

  /** Initialize your data structure here. */
  public RandomizedSet() {
    dict = new HashMap();
    list = new ArrayList();
  }

  /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
  public boolean insert(int val) {
    if (dict.containsKey(val)) return false;

    dict.put(val, list.size());
    list.add(list.size(), val);
    return true;
  }

  /** Removes a value from the set. Returns true if the set contained the specified element. */
  public boolean remove(int val) {
    if (! dict.containsKey(val)) return false;

    // move the last element to the place idx of the element to delete
    int lastElement = list.get(list.size() - 1);
    int idx = dict.get(val);
    list.set(idx, lastElement);
    dict.put(lastElement, idx);
    // delete the last element
    list.remove(list.size() - 1);
    dict.remove(val);
    return true;
  }

  /** Get a random element from the set. */
  public int getRandom() {
    return list.get(rand.nextInt(list.size()));
  }
}

 

VirMach 便宜 VPS

QNews

QNews