LeetCode 432 - All O(1) Data Structure

作者 QIFAN 日期 2017-02-15
LeetCode 432 - All O(1) Data Structure

原题链接: 432. All O`one Data Structure


题干

设计一个结构,使得能用 $O(1)$ 时间复杂度实现一下操作:

  • void inc(String key) 如果不存在 key ,插入且初始值为 1 ,若存在,值增加 1 。
  • void dec(String key) 如果不存在 key ,do nothing ,如果存在,若 key 所在的值为 1 ,删除该 key ,否则值减 1 。
  • String getMaxKey() 返回值最大的 key 的值,若不存在,返回 ""
  • String getMinKey() 返回值最小的 key 的值,若不存在,返回 ""

思路

假 $O(1)$

查找 $O(1)$ 是 Map ,获取最大最小 $O(1)$ 是 PriorityQueue 。略像 LRU ,结合了两种数据结构。
我的思路就是很直观的先设计一个 Node ,分别用 MapPrioeiryQueue 存。

犯了一个之前没有注意到的错误:PQ 是只有在新增元素是才会进行排序,如果只是改变其中某个节点的值,顺序并不会改变,可是再插入一次的话时间复杂度就变成了 $O(logN)$ 了,虽然过了,但这个做法实际上还是不能满足要求的。

代码:

public class AllOne {
private HashMap<String, Node> map;
private PriorityQueue<Node> maxQ;
private PriorityQueue<Node> minQ;
/** Initialize your data structure here. */
public AllOne() {
map = new HashMap<>();
maxQ = new PriorityQueue<>(new Comparator<Node>() {
public int compare(Node n1, Node n2) {
return n2.val - n1.val;
}
});
minQ = new PriorityQueue<>(new Comparator<Node>() {
public int compare(Node n1, Node n2) {
return n1.val - n2.val;
}
});
}
/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
public void inc(String key) {
if (map.containsKey(key)) {
// 需要重新插入
Node node = map.get(key);
maxQ.remove(node);
minQ.remove(node);
node.incVal();
maxQ.add(node);
minQ.add(node);
} else {
Node node = new Node(key);
map.put(key, node);
maxQ.add(node);
minQ.add(node);
}
}
/** 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)) {
return;
}
Node node = map.get(key);
if (map.get(key).val > 1) {
// 需要重新插入
maxQ.remove(node);
minQ.remove(node);
node.decVal();
maxQ.add(node);
minQ.add(node);
} else {
map.remove(key);
maxQ.remove(node);
minQ.remove(node);
node = null;
}
}
/** Returns one of the keys with maximal value. */
public String getMaxKey() {
if (maxQ.isEmpty()) {
return "";
}
return maxQ.peek().key;
}
/** Returns one of the keys with Minimal value. */
public String getMinKey() {
if (minQ.isEmpty()) {
return "";
}
return minQ.peek().key;
}
class Node{
private String key;
private int val;
public Node(String key) {
this.key = key;
this.val = 1;
}
public void incVal() {
this.val++;
}
public void decVal() {
this.val--;
}
}
}
/**
* 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();
*/

真 $O(1)$

Dicussion 里有一种做法是两个 map ,一个 keyMap 以 key 为键,值为对应的 value ,另一个 map 以 value 为键,值为设计的一个双向链节点,还有 value 下的所有 key 的集合。献上链接。Java AC all strict O(1) not average O(1), easy to read