Use TreeMap to handle cases when there are many counts (O(Log n ) time)


  • 0
    X
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Map;
    import java.util.Set;
    import java.util.SortedMap;
    import java.util.TreeMap;
    
    public class AllOne {
    	Map<String, Integer> map1;
    	SortedMap<Integer, Set<String>> map2;
    	/** Initialize your data structure here. */
    	public AllOne() {
    		map1 = new HashMap<>();
    		map2 = new TreeMap<>();
    	}
    	    
    	/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    	public void inc(String key) {
    	        if (!map1.containsKey(key)) {
    	        		map1.put(key, 1);
    	        		if (!map2.containsKey(1))
    	        			map2.put(1, new HashSet<>());
    	        		
    	        		map2.get(1).add(key);
    	        } else {
    	        		int old_cnt = map1.get(key);
    	        		int new_cnt = old_cnt + 1;
    	        		map1.put(key, new_cnt);
    	        		map2.get(old_cnt).remove(key);
    	        		// remove the key if corresponding count == 0
    	        		if (map2.get(old_cnt).isEmpty())
    	        			map2.remove(old_cnt);
    	        		if (!map2.containsKey(new_cnt))
    	        			map2.put(new_cnt, new HashSet<>());
    	        		map2.get(new_cnt).add(key);
    	        }
    	}
    	    
    	/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    	public void dec(String key) {
    		if (!map1.containsKey(key))
    			return;
    	        int old_cnt = map1.get(key);
    	        int new_cnt = old_cnt - 1;
    	        map1.put(key, new_cnt);
    	        if (map1.get(key) == 0)
    	        		map1.remove(key);
    	        
    	        map2.get(old_cnt).remove(key);
    	        if (map2.get(old_cnt).isEmpty())
    	        		map2.remove(old_cnt);
    	        if (new_cnt > 0) {
    	        		if (!map2.containsKey(new_cnt))
    	        			map2.put(new_cnt, new HashSet<>());
    	        		map2.get(new_cnt).add(key);
    	        }
    	}
    	    
    	/** Returns one of the keys with maximal value. */
    	public String getMaxKey() {
    		if (map2.isEmpty())
    			return "";
    		return map2.get(map2.lastKey()).iterator().next();
    	}
    	    
    	/** Returns one of the keys with Minimal value. */
    	public String getMinKey() {
    		if (map2.isEmpty())
    			return "";
    		return map2.get(map2.firstKey()).iterator().next();
    	}
    }
    
    

Log in to reply
 

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