首页 > 代码库 > 43. Merge Sorted Array && LRU Cache
43. Merge Sorted Array && LRU Cache
Merge Sorted Array
OJ: https://oj.leetcode.com/problems/merge-sorted-array/
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note: You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.
思想：因为 A 很大， 所以从最大值开始插入， 即从 A 的 m+n 位置开始插入数据。避免了冗余的移动。
class Solution {public: void merge(int A[], int m, int B[], int n) { int end = m+n-1; int iA = m-1, iB = n-1; while(iB >= 0) { if(iA < 0 || A[iA] <= B[iB]) A[end--] = B[iB--]; else A[end--] = A[iA--]; } }};
LRU Cache
OJ: https://oj.leetcode.com/problems/lru-cache/
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
思想：
1. 由于要 O(1) 时间确定某 key 是不是在 Cache 中，所以用 Hash_map (<key, node*>), 从而能够O(1)找到结点地址，返回对应的 value。
2. 由于要 O(1) 时间插入、删除某项， 所以各项之间的存储不能用单链表（删除时要O(n)查找前面的结点），不能用顺序表(插入、删除都 O(n)), 故存储使用双链表。
综上分析，查找、插入、删除都是 O(1)时间。（代码尚可优化）
typedef struct node { node *pre, *next; int key; int value; node() : pre(NULL), next(NULL), key(0), value(0) {} node(int k, int v) : pre(NULL), next(NULL), key(k), value(v) {}} DoubleLinkList;class LRUCache{public: LRUCache(int capacity) : _capacity(capacity), cnt(0), front(NULL), tail(NULL) {} int get(int key) { unordered_map<int, node*>::iterator it = _map.find(key); if(it == _map.end()) return -1; node* s = it->second; if(s != front) { if(s == tail) { tail = s->pre; s->pre = NULL; tail->next = NULL; front->pre = s; s->next = front; front = s; }else { s->pre->next = s->next; s->next->pre = s->pre; s->next = front; front->pre = s; front = s; } } return it->second->value; } void set(int key, int value) { unordered_map<int, node*>::iterator it = _map.find(key); if(it == _map.end()) { if(++cnt > _capacity) { if(front == tail) { _map.erase(tail->key); front = tail = NULL; }else{ node *s = tail; tail = tail->pre; tail->next = NULL; _map.erase(s->key); free(s); --cnt; } } node *p = new node(key, value); if(front == NULL) { front = tail = p; }else { p->next = front; front->pre = p; front = p; } _map.insert(pair<int, node*>(key, p)); }else { it->second->value = http://www.mamicode.com/value;>
43. Merge Sorted Array && LRU Cache