跳至主要内容

15.3 複合資料結構

這一類題目通常採用雜湊表或有序表輔助記錄，以加速尋址；再搭配陣列或鏈結串列進行連續的資料儲存，以加速連續選址或刪除值。

146. LRU Cache​

題目描述​

設計一個固定大小的最近最少使用快取（Least Recently Used Cache, LRU）。當快取未滿時插入資料，或者查找或更新快取內已存在的資料時，將該資料標記為最近使用。在快取滿的情況下，插入新資料時需要移除最久未使用的資料，插入新資料，並將該新資料標記為最近使用。

輸入輸出範例​

以下是資料結構的調用範例。給定一個大小為 n 的快取，利用最近最少使用策略儲存資料。

LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 輸出 value 1
cache.put(3, 3); // 移除 key 2
cache.get(2); // 輸出 value -1 (未找到)
cache.put(4, 4); // 移除 key 1
cache.get(1); // 輸出 value -1 (未找到)
cache.get(3); // 輸出 value 3
cache.get(4); // 輸出 value 4

題解​

我們採用一個鏈結串列來儲存資料的 key 和 value，鏈結串列的連結順序即為最近使用的新舊順序，最新的資料在鏈結串列的頭節點。同時我們需要一個雜湊表進行查找，其鍵是資料的 key，值是其在鏈結串列中的對應指標/迭代器。每次查找成功（cache hit）時，需要將指標/迭代器對應的節點移動到鏈結串列的頭節點。

class LRUCache {
   public:
    LRUCache(int capacity) : n_(capacity) {}

    int get(int key) {
        auto it = key_to_cache_it_.find(key);
        if (it == key_to_cache_it_.end()) {
            return -1;
        }
        cache_.splice(cache_.begin(), cache_, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = key_to_cache_it_.find(key);
        if (it != key_to_cache_it_.end()) {
            it->second->second = value;
            return cache_.splice(cache_.begin(), cache_, it->second);
        }
        cache_.insert(cache_.begin(), make_pair(key, value));
        key_to_cache_it_[key] = cache_.begin();
        if (cache_.size() > n_) {
            key_to_cache_it_.erase(cache_.back().first);
            cache_.pop_back();
        }
    }

   private:
    list<pair<int, int>> cache_;
    unordered_map<int, list<pair<int, int>>::iterator> key_to_cache_it_;
    int n_;
};

對於 Python 而言，我們還可以直接利用 OrderedDict 函數實現 LRU，這將大大簡化題目的難度。不過，筆者希望讀者還是能仔細研讀以上的解題說明，深入了解 LRU 實現的核心原理。

class LRUCache:
    def __init__(self, capacity: int):
        self.n = capacity
        self.cache = {}

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache[key] = self.cache.pop(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.pop(key)
        self.cache[key] = value
        if len(self.cache) > self.n:
            self.cache.pop(next(iter(self.cache)))

複雜度分析​

  • 時間複雜度:

    • get 操作: 平均 O(1)O(1)，但因為使用的是內建 dict 搭配 pop() 和 iter()，在某些 Python 實作中可能會有最壞 O(n)O(n)。
    • put 操作: 平均 O(1)O(1)，但 pop(next(iter(...))) 同樣可能在最壞情況下達到 O(n)O(n)。

  • 空間複雜度: O(n)O(n)，其中 nn 是快取容量 capacity，用來儲存最多 nn 個鍵值對。

380. Insert Delete GetRandom O(1)​

題目描述​

設計一個插入、刪除和隨機取值均為 O(1)O(1) 時間複雜度的資料結構。

輸入輸出範例​

以下是資料結構的調用範例。

RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1);
randomizedSet.remove(2);
randomizedSet.insert(2);
randomizedSet.getRandom(); // 50% 1, 50% 2
randomizedSet.remove(1);
randomizedSet.insert(2);
randomizedSet.getRandom(); // 100% 2

題解​

我們採用一個陣列儲存插入的數字，同時利用一個雜湊表查找位置。每次插入數字時，直接加入陣列，且將位置記錄在雜湊表中。每次刪除數字時，將當前陣列最後一位與刪除位互換，並更新雜湊表。隨機取值時，則可以在陣列內任意選取位置。

class RandomizedSet {
   public:
    bool insert(int val) {
        if (v_to_k_.contains(val)) {
            return false;
        }
        v_to_k_[val] = nums_.size();
        nums_.push_back(val);
        return true;
    }

    bool remove(int val) {
        if (!v_to_k_.contains(val)) {
            return false;
        }
        v_to_k_[nums_.back()] = v_to_k_[val];
        nums_[v_to_k_[val]] = nums_.back();
        v_to_k_.erase(val);
        nums_.pop_back();
        return true;
    }

    int getRandom() { return nums_[rand() % nums_.size()]; }

   private:
    unordered_map<int, int> v_to_k_;
    vector<int> nums_;
};

複雜度分析​

  • 時間複雜度:

    • insert: O(1)O(1)，使用雜湊表檢查是否存在並在陣列末尾加入元素。
    • remove: O(1)O(1)，將待刪除元素與最後一個元素交換位置後移除，並更新雜湊表。
    • getRandom: O(1)O(1)，隨機從陣列中取值。

  • 空間複雜度: O(n)O(n)，其中 nn 是集合中最多的元素數量，儲存在 nums 與 v_to_k 中。