structNode{intcount;unordered_set<string>keys;};classAllOne{public:voidinc(stringkey){if(constautoit=keyToIterator.find(key);it==keyToIterator.end())addNewKey(key);elseincrementExistingKey(it,key);}voiddec(stringkey){constautoit=keyToIterator.find(key);// It is guaranteed that key exists in the data structure before the// decrement.decrementExistingKey(it,key);}stringgetMaxKey(){returnnodeList.empty()?"":*nodeList.back().keys.begin();}stringgetMinKey(){returnnodeList.empty()?"":*nodeList.front().keys.begin();}private:list<Node>nodeList;// list of nodes sorted by countunordered_map<string,list<Node>::iterator>keyToIterator;// Adds a new node with count 1.voidaddNewKey(conststring&key){if(nodeList.empty()||nodeList.front().count>1)nodeList.push_front({1,{key}});else// nodeList.front().count == 1nodeList.front().keys.insert(key);keyToIterator[key]=nodeList.begin();}// Increments the count of the key by 1.voidincrementExistingKey(unordered_map<string,list<Node>::iterator>::iteratorit,conststring&key){constautolistIt=it->second;autonextIt=next(listIt);constintnewCount=listIt->count+1;if(nextIt==nodeList.end()||nextIt->count>newCount)nextIt=nodeList.insert(nextIt,{newCount,{key}});else// Node with count + 1 exists.nextIt->keys.insert(key);keyToIterator[key]=nextIt;remove(listIt,key);}// Decrements the count of the key by 1.voiddecrementExistingKey(unordered_map<string,list<Node>::iterator>::iteratorit,conststring&key){constautolistIt=it->second;if(listIt->count==1){keyToIterator.erase(it);remove(listIt,key);return;}autoprevIt=prev(listIt);constintnewCount=listIt->count-1;if(listIt==nodeList.begin()||prevIt->count<newCount)prevIt=nodeList.insert(listIt,{newCount,{key}});else// Node with count - 1 exists.prevIt->keys.insert(key);keyToIterator[key]=prevIt;remove(listIt,key);}// Removes the key from the node list.voidremove(list<Node>::iteratorit,conststring&key){it->keys.erase(key);if(it->keys.empty())nodeList.erase(it);}};
classNode{publicintcount;publicSet<String>keys=newHashSet<>();publicNodeprev=null;publicNodenext=null;publicNode(intcount){this.count=count;}publicNode(intcount,Stringkey){this.count=count;keys.add(key);}}classAllOne{publicAllOne(){head.next=tail;tail.prev=head;}publicvoidinc(Stringkey){if(keyToNode.containsKey(key))incrementExistingKey(key);elseaddNewKey(key);}publicvoiddec(Stringkey){// It is guaranteed that key exists in the data structure before the// decrement.decrementExistingKey(key);}publicStringgetMaxKey(){returntail.prev==head?"":tail.prev.keys.iterator().next();}publicStringgetMinKey(){returnhead.next==tail?"":head.next.keys.iterator().next();}privateMap<String,Node>keyToNode=newHashMap<>();privateNodehead=newNode(0);privateNodetail=newNode(0);// Adds a new node with frequency 1.privatevoidaddNewKey(finalStringkey){if(head.next.count==1)head.next.keys.add(key);elseinsertAfter(head,newNode(1,key));keyToNode.put(key,head.next);}// Increments the frequency of the key by 1.privatevoidincrementExistingKey(finalStringkey){Nodenode=keyToNode.get(key);node.keys.remove(key);if(node.next==tail||node.next.count>node.count+1)insertAfter(node,newNode(node.count+1));node.next.keys.add(key);keyToNode.put(key,node.next);if(node.keys.isEmpty())remove(node);}// Decrements the count of the key by 1.privatevoiddecrementExistingKey(finalStringkey){Nodenode=keyToNode.get(key);node.keys.remove(key);if(node.count>1){if(node.prev==head||node.prev.count!=node.count-1)insertAfter(node.prev,newNode(node.count-1));node.prev.keys.add(key);keyToNode.put(key,node.prev);}else{keyToNode.remove(key);}if(node.keys.isEmpty())remove(node);}privatevoidinsertAfter(Nodenode,NodenewNode){newNode.prev=node;newNode.next=node.next;node.next.prev=newNode;node.next=newNode;}privatevoidremove(Nodenode){node.prev.next=node.next;node.next.prev=node.prev;}}
fromdataclassesimportdataclass@dataclassclassNode:def__init__(self,count:int,key:str|None=None):self.count=countself.keys:set[str]={key}ifkeyelseset()self.prev:Node|None=Noneself.next:Node|None=Nonedef__eq__(self,other)->bool:ifnotisinstance(other,Node):returnNotImplementedreturnself.count==other.countandself.keys==other.keysclassAllOne:def__init__(self):self.keyToNode:dict[str,Node]={}self.head=Node(0)self.tail=Node(0)self.head.next=self.tailself.tail.prev=self.headdefinc(self,key:str)->None:ifkeyinself.keyToNode:self._incrementExistingKey(key)else:self._addNewKey(key)defdec(self,key:str)->None:# It is guaranteed that key exists in the data structure before the# decrement.self._decrementExistingKey(key)defgetMaxKey(self)->str:return''ifself.tail.prev==self.head \
elsenext(iter(self.tail.prev.keys))defgetMinKey(self)->str:return''ifself.head.next==self.tail \
elsenext(iter(self.head.next.keys))def_addNewKey(self,key:str)->None:"""Adds a new node with frequency 1."""ifself.head.next.count==1:self.head.next.keys.add(key)else:self._insertAfter(self.head,Node(1,key))self.keyToNode[key]=self.head.nextdef_incrementExistingKey(self,key:str)->None:"""Increments the frequency of the key by 1."""node=self.keyToNode[key]node.keys.remove(key)ifnode.next==self.tailornode.next.count>node.count+1:self._insertAfter(node,Node(node.count+1))node.next.keys.add(key)self.keyToNode[key]=node.nextifnotnode.keys:self._remove(node)def_decrementExistingKey(self,key:str)->None:"""Decrements the count of the key by 1."""node=self.keyToNode[key]node.keys.remove(key)ifnode.count>1:ifnode.prev==self.headornode.prev.count!=node.count-1:self._insertAfter(node.prev,Node(node.count-1))node.prev.keys.add(key)self.keyToNode[key]=node.prevelse:delself.keyToNode[key]ifnotnode.keys:self._remove(node)def_insertAfter(self,node:Node,newNode:Node)->None:newNode.prev=nodenewNode.next=node.nextnode.next.prev=newNodenode.next=newNodedef_remove(self,node:Node)->None:node.prev.next=node.nextnode.next.prev=node.prev
Thanks for stopping by! If you find this site helpful, consider buying me some protein powder to keep me fueled! π