Java solutions of three different ways. PriorityQueue : O(capacity) TreeMap : O(log(capacity)) DoubleLinkedList : O(1)

• The first one: PriorityQueue + HashMap set O(capacity) get O(capacity)
The second one: TreeMap + HashMap set O(log(capacity)) get O(log(capacity))
The third one: HashMap + HashMap + DoubleLinkedList set O(1) get O(1)

PriorityQueue + HashMap: set O(capacity) get O(capacity)
'''

``````long stamp;
int capacity;
int num;
PriorityQueue<Pair> minHeap;
HashMap<Integer, Pair> hashMap;

// @param capacity, an integer
public LFUCache(int capacity) {
this.capacity = capacity;
num = 0;
minHeap = new PriorityQueue<Pair>();
hashMap = new HashMap<Integer, Pair>();
stamp = 0;
}

// @param key, an integer
// @param value, an integer
// @return nothing
public void set(int key, int value) {
if (capacity == 0) {
return;
}
if (hashMap.containsKey(key)) {
Pair old = hashMap.get(key);
minHeap.remove(old);

Pair newNode = new Pair(key, value, old.times + 1, stamp++);

hashMap.put(key, newNode);
minHeap.offer(newNode);
} else if (num == capacity) {
Pair old = minHeap.poll();
hashMap.remove(old.key);

Pair newNode = new Pair(key, value, 1, stamp++);

hashMap.put(key, newNode);
minHeap.offer(newNode);
} else {
num++;
Pair pair = new Pair(key, value, 1, stamp++);
hashMap.put(key, pair);
minHeap.offer(pair);
}
}

public int get(int key) {
if (capacity == 0) {
return -1;
}
if (hashMap.containsKey(key)) {
Pair old = hashMap.get(key);
minHeap.remove(old);

Pair newNode = new Pair(key, old.value, old.times + 1, stamp++);

hashMap.put(key, newNode);
minHeap.offer(newNode);
return hashMap.get(key).value;
} else {
return -1;
}
}

class Pair implements Comparable<Pair> {
long stamp;
int key;
int value;
int times;
public Pair(int key, int value, int times, long stamp) {
this.key = key;
this.value = value;
this.times = times;
this.stamp = stamp;
}

public int compareTo(Pair that) {
if (this.times == that.times) {
return (int)(this.stamp - that.stamp);
} else {
return this.times - that.times;
}
}
}
``````

'''

TreeMap + HashMap: set O(log(capacity)) get O(log(capacity))

'''

``````private int capacity;
private int stamp;
private HashMap<Integer, Tuple> hashMap;
private TreeMap<Tuple, Integer> treeMap;
public LFUCache(int capacity) {
this.capacity = capacity;
stamp = 0;
hashMap = new HashMap<Integer, Tuple>();
treeMap = new TreeMap<Tuple, Integer>(new Comparator<Tuple>() {
public int compare(Tuple t1, Tuple t2) {
if (t1.times == t2.times) {
return t1.stamp - t2.stamp;
}
return t1.times - t2.times;
}
});
}

public int get(int key) {
if (capacity == 0) {
return -1;
}
if (!hashMap.containsKey(key)) {
return -1;
}
Tuple old = hashMap.get(key);
treeMap.remove(old);
Tuple newTuple = new Tuple(old.value, stamp++, old.times + 1);
treeMap.put(newTuple, key);
hashMap.put(key, newTuple);
return old.value;
}

public void set(int key, int value) {
if (capacity == 0) {
return;
}
if (hashMap.containsKey(key)) {
Tuple old = hashMap.get(key);
Tuple newTuple = new Tuple(value, stamp++, old.times + 1);
treeMap.remove(old);
hashMap.put(key, newTuple);
treeMap.put(newTuple, key);
} else {
if (treeMap.size() == capacity) {
int endKey = treeMap.pollFirstEntry().getValue();
hashMap.remove(endKey);
}
Tuple newTuple = new Tuple(value, stamp++, 1);
hashMap.put(key, newTuple);
treeMap.put(newTuple, key);
}
}
class Tuple {
int value;
int times;
int stamp;
public Tuple (int value, int stamp, int times) {
this.value = value;
this.stamp = stamp;
this.times = times;
}
}
``````

'''
HashMap + HashMap + DoubleLinkedList: set O(1) get O(1)

map1 save the nodes in the cache
finalNodes save the newest node which has appeared ''key'' times.
Using a doubleLinkedList to save the nodes in the cache.if a node appeared more times or is a new comer, the position in the list of this node is as back as possible.

'''

``````private int capacity;
private int count;
private HashMap<Integer, Tuple> map1; // whether appeared
private HashMap<Integer, Tuple> finalNodes; // value : the final node of key times
private Tuple dummyEnd;

public LFUCache(int capacity) {
this.capacity = capacity;
count = 0;
map1 = new HashMap<Integer, Tuple>();
finalNodes = new HashMap<>();
dummyHead = new Tuple(0, 0, 0);
dummyEnd = new Tuple(0, 0, 0);
}

public int get(int key) {
if (capacity == 0 || !map1.containsKey(key)) {
return -1;
}
Tuple old = map1.get(key);
set(key, old.value);
return old.value;
}

public void set(int key, int value) {
if (capacity == 0) {
return;
}
if (map1.containsKey(key)) { // this key has appeared
Tuple cur = map1.get(key);
if (finalNodes.get(cur.times) == cur && finalNodes.get(cur.times + 1) == null) { // the position should not change
finalNodes.put(cur.times, cur.prev.times == cur.times ? cur.prev : null);
cur.times++;
cur.value = value;
finalNodes.put(cur.times, cur);
return;
}
removeNode(cur); // remove node cur
if (finalNodes.get(cur.times) == cur) {
finalNodes.put(cur.times, cur.prev.times == cur.times ? cur.prev : null);
}
cur.times++;
cur.value = value;
Tuple finalNode = finalNodes.get(cur.times) == null ? finalNodes.get(cur.times - 1) : finalNodes.get(cur.times);
insertNode(finalNode, cur);
finalNodes.put(cur.times, cur); // cur is the final node whitch appeared cur.times
} else if (count == capacity) { // reach limt of the cache
removeNode(head); //remove the first which appeared least times and is the least Used
}
Tuple cur = new Tuple(key, value, 1);
if (finalNodes.get(1) == null) {
} else {
Tuple finalNode = finalNodes.get(1);
insertNode(finalNode, cur);
}
finalNodes.put(1, cur);
map1.put(key, cur);
} else {
count++;
Tuple cur = new Tuple(key, value, 1);
if (finalNodes.get(1) == null){
} else {
Tuple finalNode = finalNodes.get(1);
insertNode(finalNode, cur);
}
finalNodes.put(1, cur);
map1.put(key, cur);
}
}

public void insertNode(Tuple t1, Tuple t2) {
t2.next = t1.next;
t1.next.prev = t2;
t1.next = t2;
t2.prev = t1;
}

public void removeNode(Tuple node) {
node.next.prev = node.prev;
node.prev.next = node.next;
}
class Tuple {
int key;
int value;
int times;
Tuple prev;
Tuple next;
public Tuple(int key, int value, int times) {
this.key = key;
this.value = value;
this.times = times;
}
}
``````

'''

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.