Java solution with sorted ArrayList and two hashMaps 98ms beat 92%


  • 0
    C
    class Tuple{
        String key;
        int val;
        Tuple(String s, int v){
            key=s;
            val=v;
        }
    }
    
    Map<String, Integer> map; //store key-> index of the following list
    List<Tuple> list; //store all (key,value) in reversing sorted value order [(a,3),(b,3),(c,2),(d,1)]
    Map<Integer, Integer> indexMap; //start index for each value, using above example (3->0),(2->2),(1,3)
    
    /** Initialize your data structure here. */
    public AllOne() {
        map = new HashMap<>();
        list = new ArrayList<>();
        indexMap = new HashMap<>();
    }
    
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        if(map.containsKey(key)){
            //swap curr with the first element which val equals curr.val
            int i = map.get(key);
            Tuple curr = list.get(i);
            int first=indexMap.get(curr.val);
            Tuple exchange =list.get(first);
            list.set(i, exchange);
            list.set(first, curr);
            map.put(key, first);
            map.put(exchange.key, i);
            
            //update curr val index
            indexMap.put(curr.val, first+1);
            
            //increase val, if it is a new val, put 0 in index map
            curr.val++;
            if(!indexMap.containsKey(curr.val)) indexMap.put(curr.val, 0);
        }else{
            //if a new key, add to the last of list
            Tuple t = new Tuple(key, 1);
            list.add(t);
            map.put(key, list.size()-1);
            indexMap.putIfAbsent(1,0);
        }
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        if(map.containsKey(key)){
            int i=map.get(key);
            Tuple curr = list.get(i);
            if(curr.val==1){
                Tuple last = list.get(list.size()-1);
                list.set(i, last);
                list.remove(list.size()-1);
                map.put(last.key, i);
                map.remove(key);
            }else{
                //swap curr with the last element which val equals curr.val
                int index = indexMap.get(curr.val-1)-1;
                Tuple exchange = list.get(index);
                list.set(i, exchange);
                list.set(index, curr);
                map.put(key, index);
                map.put(exchange.key, i);
                if(index==0) indexMap.remove(curr.val);
                curr.val--;
                indexMap.put(curr.val, index);
            }
        }
    }
    
    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        if(!list.isEmpty()) return list.get(0).key;
        return "";
    }
    
    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        if(!list.isEmpty()) return list.get(list.size()-1).key;
        return "";
    }

Log in to reply
 

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