All O`one Data Structure
写一个全是O(1)的数据结构
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();
*/