share my Java Solution!


  • 1
    T
    class AllOne {
        
       class bucket{
           LinkedHashSet<String> set;
           int count;
           bucket pre,next;
           bucket(int count){
               set = new LinkedHashSet<>();
               this.count = count;
           }
       }
        
        Map<Integer,bucket> countMap = new HashMap<>();
        Map<String,Integer> map = new HashMap<>();
        bucket head;
        bucket tail;
        /** Initialize your data structure here. */
        public AllOne() {
            head = new bucket(0);
            tail = new bucket(0);
            tail.pre = head;
            head.next = tail;
            head.set.add("");
            countMap.put(0,head);
        }
        
        
        public void deleteBucket(bucket node){
            bucket pre_node = node.pre;
            pre_node.next = node.next;
            node.next.pre = pre_node;
        }
        
        public void addBucket(bucket pre_node, bucket node){
            bucket nextnode = pre_node.next;
            node.next = nextnode;
            nextnode.pre = node;
            node.pre = pre_node;
            pre_node.next = node;
        }
        
        public void addBucket2(bucket node,bucket next_node){
            bucket pre_node = next_node.pre;
            pre_node.next = node;
            node.pre = pre_node;
            node.next = next_node;
            next_node.pre = node;
        }
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
              int count = map.getOrDefault(key,0);
              if(!countMap.containsKey(count+1)){
                   bucket newbucket = new bucket(count+1);
                   countMap.put(count+1,newbucket);
                   addBucket(countMap.get(count),newbucket);
              }
              countMap.get(count+1).set.add(key);
            
             if(count!=0){
                  countMap.get(count).set.remove(key);
                  if(countMap.get(count).set.size()==0){
                      deleteBucket(countMap.get(count));
                      countMap.remove(count);
                  }
              }
              map.put(key,count+1);
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        public void dec(String key) {
            int count = map.getOrDefault(key,0);
           if(count==0){
               return;
           }
            if(count==1){
                countMap.get(1).set.remove(key);
                map.remove(key);
                if(countMap.get(1).set.size()==0){
                    deleteBucket(countMap.get(1));
                    countMap.remove(1);
                }
            }else{
                
                if(!countMap.containsKey(count-1)){
                    bucket node = new bucket(count-1);
                    countMap.put(count-1,node);
                    addBucket2(node,countMap.get(count));
                }
                countMap.get(count-1).set.add(key);
                map.put(key,count-1);
                countMap.get(count).set.remove(key);
                if(countMap.get(count).set.size()==0){
                    deleteBucket(countMap.get(count));
                    countMap.remove(count);
                }
            }
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
             if(tail.pre == head){
                 return "";
             }
             return (String)tail.pre.set.iterator().next();   
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
             if(head.next == tail){
                 return "";
             }
             return (String)head.next.set.iterator().next();  
        } 
    }
    
    /**
     * Your AllOne object will be instantiated and called as such:
     * AllOne obj = new AllOne();
     * obj.inc(key);
     * obj.dec(key);
     * String param_3 = obj.getMaxKey();
     * String param_4 = obj.getMinKey();
     */
    

Log in to reply
 

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