跳至主要内容

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)))

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_;
};