跳到主要内容

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