All O`one Data Structure
写一个全是O(1)的数据结构
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
public class AllOne {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 ""; } } /** * 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(); */ |