# My O(1) solution in java, easy to understand!

• To solve this problem, I keep two maps and a value;
map1 : HashMap<Integer,ListNode>, used to store node key and the node
map2: HashMap<Integer,Pair>, a Pair represent to a double linked-list(head, tail). The key is time "t" and value is a linked-list storing nodes who has been called "t" times;

value low: keep the smallest time. Use this value to make a decision which node we should delete.

hope it helps~

``````public class LFUCache {
public class ListNode {
ListNode pre;
ListNode next;
int id;
int val;
int time;
public ListNode(int id , int val , int time) {
this.id = id;
this.val = val;
this.time = time;
}
}
public class Pair {
ListNode tail;
public Pair(ListNode head , ListNode tail) {
this.tail = tail;
}
}
HashMap<Integer,ListNode> map = new HashMap<Integer,ListNode>();
HashMap<Integer,Pair> timemap = new HashMap<Integer,Pair>();
int capacity;
int low = -1;
public LFUCache(int capacity) {
this.capacity = capacity;
}

public int get(int key) {
if(capacity <= 0 || !map.containsKey(key)) return -1;
int res = map.get(key).val;
ListNode node = map.get(key);
int time = node.time;
Pair p = timemap.get(time);
//doing original node remove
if(node.pre == p.head && node.next == p.tail) {
timemap.remove(time);
if(low == time) {
low++;
}
}else {
ListNode tp = node.pre;
ListNode tn = node.next;
tp.next = tn;
tn.pre = tp;
}

//doning new node insert
ListNode newnode = new ListNode(key , res , time+1);
if(timemap.containsKey(time+1)) {
Pair p2 = timemap.get(time+1);

t.pre = newnode;

newnode.next = t;
}else {
ListNode head = new ListNode(-1 , -1 , -1);
ListNode tail = new ListNode(-1 , -1 , -1);
tail.pre = newnode;
newnode.next = tail;
timemap.put(time+1 , new Pair(head , tail));
}
map.put(key , newnode);
return res;
}

public void put(int key, int value) {
if(capacity <= 0) return;
if(map.containsKey(key)) {  //remove the original node with original time and insert a new node with time+1
//doning original node remove
ListNode node = map.get(key);
int time = node.time;
Pair p = timemap.get(time);
//if it is the only node with key time in the timemap, just remove this timekry from timemap
if(node.pre == p.head && node.next == p.tail) {
timemap.remove(time);
if(low == time) {
low++;
}
}else {//if it is not the only node, just remove it
ListNode tp = node.pre;
ListNode tn = node.next;
tp.next = tn;
tn.pre = tp;
}

//doning new node insert
ListNode newnode = new ListNode(key , value , time+1);
if(timemap.containsKey(time+1)) {
Pair p2 = timemap.get(time+1);

t.pre = newnode;

newnode.next = t;
}else {
ListNode head = new ListNode(-1 , -1 , -1);
ListNode tail = new ListNode(-1 , -1 , -1);
tail.pre = newnode;
newnode.next = tail;
timemap.put(time+1 , new Pair(head , tail));
}
map.put(key , newnode);

}else {
//doning original node remove
if(map.size() >= capacity) {
Pair p = timemap.get(low);
ListNode removenode = p.tail.pre;
ListNode n = p.tail.pre.pre;
n.next = p.tail;
p.tail.pre = n;
map.remove(removenode.id);
timemap.remove(low);
}
}
low = 1;

//doing new node insert.
ListNode newnode = new ListNode(key , value , 1);
if(timemap.containsKey(1)) {
Pair p = timemap.get(1);

t.pre = newnode;

newnode.next = t;
}else {
ListNode head = new ListNode(-1 , -1 , -1);
ListNode tail = new ListNode(-1 , -1 , -1);
tail.pre = newnode;
newnode.next = tail;
timemap.put(1 , new Pair(head , tail));
}
map.put(key , newnode);
}
}
}

/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/``````

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