432. 全 O(1) 的数据结构
432. 全 O(1) 的数据结构
🔴 🔖 设计
哈希表
链表
双向链表
🔗 力扣
LeetCode
题目
Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.
Implement the AllOne
class:
AllOne()
Initializes the object of the data structure.inc(String key)
Increments the count of the stringkey
by1
. Ifkey
does not exist in the data structure, insert it with count1
.dec(String key)
Decrements the count of the stringkey
by1
. If the count ofkey
is0
after the decrement, remove it from the data structure. It is guaranteed thatkey
exists in the data structure before the decrement.getMaxKey()
Returns one of the keys with the maximal count. If no element exists, return an empty string""
.getMinKey()
Returns one of the keys with the minimum count. If no element exists, return an empty string""
.
Note that each function must run in O(1)
average time complexity.
Example 1:
Input
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
Output
[null, null, null, "hello", "hello", null, "hello", "leet"]
Explanation
AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "hello"
allOne.inc("leet");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "leet"
Constraints:
1 <= key.length <= 10
key
consists of lowercase English letters.- It is guaranteed that for each call to
dec
,key
is existing in the data structure. - At most
5 * 10^4
calls will be made toinc
,dec
,getMaxKey
, andgetMinKey
.
题目大意
请你设计一个用于存储字符串计数的数据结构,并能够返回计数最小和最大的字符串。
实现 AllOne
类:
AllOne()
初始化数据结构的对象。inc(String key)
字符串key
的计数增加1
。如果数据结构中尚不存在key
,那么插入计数为1
的key
。dec(String key)
字符串key
的计数减少1
。如果key
的计数在减少后为 0 ,那么需要将这个key
从数据结构中删除。测试用例保证:在减少计数前,key
存在于数据结构中。getMaxKey()
返回任意一个计数最大的字符串。如果没有元素存在,返回一个空字符串""
。getMinKey()
返回任意一个计数最小的字符串。如果没有元素存在,返回一个空字符串""
。
注意:每个函数都应当满足 O(1)
平均时间复杂度。
解题思路
这道题可以用 哈希表 + 双向链表 来解决。
- 链表中的每个节点存储一个字符串集合
keys
,和一个正整数count
,表示keys
中的字符串均出现count
次。注意,count
相同的字符串存储在同一个节点中。 - 链表从头到尾的每个节点的
count
值单调递增(但不一定连续)。 - 每个节点还需存储指向上一个节点的指针
prev
和指向下一个节点的指针next
。 - 另外还要用一个哈希表
map
维护每个字符串当前所处的链表节点。
- 对于
inc
操作:
当若
key
不在链表中,判断当前链表有没有count = 1
的节点。因为链表是按照count
升序排列的,所以只需要看头节点的count
是否为1
;- 若有则共用此节点;
- 否则新建一个
count = 1
的节点;
若
key
在链表中,设key
所在节点为cur
,判断当前链表有没有count = cur.count + 1
的节点。同理也只需要判断cur.next
的count
是否等于cur.count + 1
;- 若有则共用此
cur.next
节点; - 否则新建一个
count = cur.count + 1
的节点插入到 cur 的后面; - 最后,将
key
从cur.keys
中移除,若移除后 cur.keys 为空,则将 cur 从链表中移除。并更新map
中key
所处的节点。
- 若有则共用此
- 对于
dec
操作:
- 若
key
仅出现一次:将其从map
中移除。 - 若
key
出现不止一次,则需要判断链表中是否有count = cur.count - 1
的节点.- 若有,则共用此
cur.prev
节点; - 否则新建一个
count = cur.count - 1
的节点;
- 若有,则共用此
- 最后,将
key
从cur.keys
中移除,若移除后cur.keys
为空,则将cur
从链表中移除。
- 对于
getMaxKey
操作:
- 在链表不为空时,返回链表尾节点的
keys
中的任一元素; - 否则返回空字符串。
- 对于
getMinKey
操作
- 在链表不为空时,返回链表头节点的
keys
中的任一元素; - 否则返回空字符串。
复杂度分析
- 时间复杂度:所有操作均为
O(1)
,这里将字符串长度视作常数。 - 空间复杂度:
O(n)
,其中n
是调用inc
的次数。最坏情况下每次调用inc
传入的字符串均不相同,我们需要O(n)
大小的哈希表来存储所有字符串。
代码
class Node {
constructor(key, count) {
this.keys = new Set([key || '']);
this.count = count || 0;
}
insert(node) {
node.prev = this;
node.next = this.next;
node.prev.next = node;
node.next.prev = node;
return node;
}
remove() {
this.next.prev = this.prev;
this.prev.next = this.next;
}
}
var AllOne = function () {
this.map = new Map();
this.root = new Node('', 0);
this.root.next = this.root;
this.root.prev = this.root;
};
/**
* @param {string} key
* @return {void}
*/
AllOne.prototype.inc = function (key) {
// key 在链表中
if (this.map.has(key)) {
let cur = this.map.get(key),
next = cur.next;
if (next == this.root || next.count > cur.count + 1) {
this.map.set(key, cur.insert(new Node(key, cur.count + 1)));
} else {
next.keys.add(key);
this.map.set(key, next);
}
cur.keys.delete(key);
if (cur.keys.size == 0) {
cur.remove();
}
}
// key 不在链表中
else {
if (this.root.next === this.root || this.root.next.count > 1) {
this.map.set(key, this.root.insert(new Node(key, 1)));
} else {
this.root.next.keys.add(key);
this.map.set(key, this.root.next);
}
}
};
/**
* @param {string} key
* @return {void}
*/
AllOne.prototype.dec = function (key) {
const cur = this.map.get(key);
// count 为 1 时,直接删掉
if (cur.count == 1) {
this.map.delete(key);
}
// count 大于 1 时,寻找 dec 后 key 在链表中的位置
else {
const prev = cur.prev;
if (prev == this.root || prev.count < cur.count - 1) {
this.map.set(key, prev.insert(new Node(key, cur.count - 1)));
} else {
prev.keys.add(key);
this.map.set(key, prev);
}
}
cur.keys.delete(key);
if (cur.keys.size == 0) {
cur.remove();
}
};
/**
* @return {string}
*/
AllOne.prototype.getMaxKey = function () {
if (!this.root.prev) return '';
let maxKey = '';
for (let key of this.root.prev.keys) {
maxKey = key;
break;
}
return maxKey;
};
/**
* @return {string}
*/
AllOne.prototype.getMinKey = function () {
if (!this.root.next) return '';
let minKey = '';
for (let key of this.root.next.keys) {
minKey = key;
break;
}
return minKey;
};
/**
* Your AllOne object will be instantiated and called as such:
* var obj = new AllOne()
* obj.inc(key)
* obj.dec(key)
* var param_3 = obj.getMaxKey()
* var param_4 = obj.getMinKey()
*/