LRUCache 之问
LRUCache之问
今天面了拼多多，LRUCache再次出现在了我的面前，面对这个半年以来面对最多的面试代码问题，我给出我的解决方案：
1、链表
使用链表作为最主要的数据结构，将数据按照先后顺序在链表尾部插入，直到满了开始从头减去链表，时间复杂度分析分别为：
| get | O(n) |
|---|---|
| add | O(n) |
| remove | O(n) |
使用单向链表，get需要找到我们要的cache所在位置，因此时间复杂度为O(n),add由于需要先判断是否已经存在，所以需要调用get方法，在满的时候需要remove，所以虽然删除时间复杂度为O(1)，整体时间复杂度为O(n),而remove从头部删除时间复杂度为O(1)但是在中间的时候需要做get操作，时间复杂度依旧为O(n)。使用双向链表可以降低add()时间复杂度，但是整体来说时间复杂度在O(n).
2、HashMap + LinkedList
使用双向链表保存数据，使用HashMap保存数据在LinkedList中的位置，时间复杂度如下：
| get | O(1) |
|---|---|
| add | O(1) |
| remove | O(1) |
学而思公司福利 381人发布