LC432. All O`one Data Structure
Implement a data structure supporting the following operations:
- Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
- Dec(Key) - If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
- GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string
"". - GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string
"".
Challenge: Perform all these in O(1) time complexity.
要求实现一个所有操作都是O(1)的数据结构，能够满足插入／删除／增减的方法。
Naive solution：
和前面那个LFU一样，自己设计Node存count对应的keys，用两个HashMap分别记录key, value和 value, Node的匹配。我觉得我写的都是O(n)操作啊，为什么是244ms。
public class AllOne {
class Node{
int count;
Set<String> keys;
Node larger;
Node smaller;
public Node(int c){
count = c;
keys = new HashSet<String>();
larger = null;
smaller = null;
}
}
Node min, max;
Map<Integer, Node> valMap;
Map<String, Integer> keyMap;
/** Initialize your data structure here. */
public AllOne() {
min = null;
max = null;
valMap = new HashMap<>();
keyMap = new HashMap<>();
}
public void inc(String key) {
//assert(keyMap != null);
//System.out.println(keyMap.size());
if(keyMap.containsKey(key)){
incKey(key, 1);
}else{
keyMap.put(key, 1);
if(min == null){
Node cur = new Node(1);
cur.keys.add(key);
min = cur;
valMap.put(1, cur);
}else if(min.count != 1){
Node cur = new Node(1);
cur.keys.add(key);
cur.larger = min;
min.smaller = cur;
min = cur;
valMap.put(1, cur);
}else{
min.keys.add(key);
}
} // else
if(max == null){
max = valMap.get(1);
}
} // inc
/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
public void dec(String key) {
if(!keyMap.containsKey(key)) return;
int cnt = keyMap.get(key);
if(cnt == 1){
removeKey(key);
}else{
incKey(key, -1);
}
}
/** Returns one of the keys with maximal value. */
public String getMaxKey() {
if(max == null || keyMap.size() == 0) return "";
for(String key: max.keys) return key;
return "";
}
/** Returns one of the keys with Minimal value. */
public String getMinKey() {
if(min == null || keyMap.size() == 0) return "";
for(String key: min.keys) return key;
return "";
}
private void incKey(String key, int num){
int val = keyMap.get(key);
Node cur = valMap.get(val);
keyMap.put(key, val + num);
if(num > 0){
if(cur == max){
Node next = new Node(val + num);
next.keys.add(key);
max = next;
cur.larger = next;
next.smaller = cur;
valMap.put(val + num, next);
}else if(cur.larger.count == val + num){
cur.larger.keys.add(key);
}else{
Node next = new Node(val + num);
next.keys.add(key);
next.larger = cur.larger;
cur.larger.smaller = next;
next.smaller = cur;
cur.larger = next;
valMap.put(val + num, next);
}
}else{
if(cur == min){
Node pre = new Node(val + num);
pre.keys.add(key);
min = pre;
cur.smaller = pre;
pre.larger = cur;
valMap.put(val + num, pre);
}else if(cur.smaller.count == val + num){
cur.smaller.keys.add(key);
}else{
Node pre = new Node(val + num);
pre.keys.add(key);
pre.smaller = cur.smaller;
cur.smaller.larger = pre;
pre.larger = cur;
cur.smaller = pre;
valMap.put(val + num, pre);
}
}
cur.keys.remove(key);
if(cur.keys.size() == 0){
valMap.remove(val);
removeNode(cur);
}
} // incKey
private void removeKey(String key){
int val = keyMap.get(key);
Node cur = valMap.get(val);
assert(cur.keys != null);
keyMap.remove(key);
cur.keys.remove(key);
if(cur.keys.size() == 0){
valMap.remove(val);
removeNode(cur);
}
} // removeKey
private void removeNode(Node cur){
if(cur == min && cur == max){
min = null;
max = null;
return;
}else if(cur == min){
min = cur.larger;
cur.larger.smaller = null;
cur = null;
}else if(cur == max){
max = cur.smaller;
cur.smaller.larger = null;
}else{
cur.smaller.larger = cur.larger;
cur.larger.smaller = cur.smaller;
cur = null;
}
return;
} // removeNode
}
/**
* 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();
*/
看了一下discuss，基本上思路一致，不过也许用java 的API会比自己写的Node结构更快一些？毕竟Node是想用LinkedHashSet一类的结构，如果iterator的话也是O(1).
Other solution：
贴一个快一些的实现吧：
Map<String, Integer> value;
TreeMap<Integer, HashSet<String>> set;
public AllOne() {
value = new HashMap<>();
set = new TreeMap<>();
}
public void inc(String key) {
if(value.containsKey(key)){
int val = value.get(key);
if(set.containsKey(val)){
HashSet<String> valSet = set.get(val);
valSet.remove(key);
if(valSet.isEmpty())
set.remove(val);
}
value.put(key, val+1);
if(set.containsKey(val+1)){
set.get(val+1).add(key);
} else {
HashSet<String> valSet = new HashSet<>();
valSet.add(key);
set.put(val+1, valSet);
}
} else {
value.put(key, 1);
if(set.containsKey(1)){
set.get(1).add(key);
} else {
HashSet<String> valSet = new HashSet<>();
valSet.add(key);
set.put(1, valSet);
}
}
}
public void dec(String key) {
if(value.containsKey(key)){
int val = value.get(key);
if(set.containsKey(val)){
HashSet<String> valSet = set.get(val);
valSet.remove(key);
if(valSet.isEmpty())
set.remove(val);
}
if(val == 1){
value.remove(key);
return;
}
value.put(key, val-1);
if(set.containsKey(val-1)){
set.get(val-1).add(key);
} else {
HashSet<String> valSet = new HashSet<>();
valSet.add(key);
set.put(val-1, valSet);
}
}
}
public String getMaxKey() {
if(set.isEmpty())
return "";
HashSet<String> value = set.lastEntry().getValue();
if(value.isEmpty())
return "";
else
return value.iterator().next();
}
public String getMinKey() {
if(set.isEmpty())
return "";
HashSet<String> value = set.firstEntry().getValue();
if(value.isEmpty())
return "";
else
return value.iterator().next();
}
看起来简洁了不少也快了好多。