Java easy understand solution


  • 0
    R
    public class AllOne {
        
        // for each key, int[0] record its number, int[1] record its place in the arraylist
        Map<String, int[]> hs;
        // string with least number in the arraylist's head, string with biggest number in the arraylist's tail
        List<String> al;
    
        /** Initialize your data structure here. */
        public AllOne() {
            hs = new HashMap<>();
            al = new ArrayList<>();
        }
        
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            if(!hs.containsKey(key)) {
                int i = 0;
                for(; i<al.size(); i++) {
                    if(hs.get(al.get(i))[0] >= 1) break;
                }
                al.add(i, key);
                for(int j = i+1; j<al.size(); j++) {
                    hs.get(al.get(j))[1]++;
                }
                hs.put(key, new int[]{1, i});
            } else {
                int i = hs.get(key)[1];
                int num = hs.get(key)[0]+1;
                al.remove(i);
                for(;i<al.size(); i++) {
                    if(hs.get(al.get(i))[0] >= num) break;
                    hs.get(al.get(i))[1]--;
                }
                al.add(i, key);
                hs.put(key, new int[]{num, i});
            }
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        public void dec(String key) {
            if(hs.containsKey(key)) {
                int i = hs.get(key)[1];
                int num = hs.get(key)[0]-1;
                al.remove(i);
                if(num == 0) {
                    hs.remove(key);
                    for(int j = i; j<al.size(); j++) {
                        hs.get(al.get(j))[1]--;
                    }
                } else {
                    i--;
                    for(; i>=0; i--) {
                        if(hs.get(al.get(i))[0]<=num) break;
                        hs.get(al.get(i))[1]++;
                    }
                    al.add(i+1, key);
                    hs.put(key, new int[]{num, i+1});
                }
            }
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            if(al.size() == 0) return "";
            return al.get(al.size()-1);
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            if(al.size() == 0) return "";
            return al.get(0);    
        }
    }
    

Log in to reply
 

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