Description#
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 string key by 1. If key does not exist in the data structure, insert it with count 1.dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key 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 <= 10key consists of lowercase English letters.- It is guaranteed that for each call to
dec, key is existing in the data structure. - At most
5 * 104 calls will be made to inc, dec, getMaxKey, and getMinKey.
Solutions#
Solution 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
| class Node:
def __init__(self, key='', cnt=0):
self.prev = None
self.next = None
self.cnt = cnt
self.keys = {key}
def insert(self, node):
node.prev = self
node.next = self.next
node.prev.next = node
node.next.prev = node
return node
def remove(self):
self.prev.next = self.next
self.next.prev = self.prev
class AllOne:
def __init__(self):
self.root = Node()
self.root.next = self.root
self.root.prev = self.root
self.nodes = {}
def inc(self, key: str) -> None:
root, nodes = self.root, self.nodes
if key not in nodes:
if root.next == root or root.next.cnt > 1:
nodes[key] = root.insert(Node(key, 1))
else:
root.next.keys.add(key)
nodes[key] = root.next
else:
curr = nodes[key]
next = curr.next
if next == root or next.cnt > curr.cnt + 1:
nodes[key] = curr.insert(Node(key, curr.cnt + 1))
else:
next.keys.add(key)
nodes[key] = next
curr.keys.discard(key)
if not curr.keys:
curr.remove()
def dec(self, key: str) -> None:
root, nodes = self.root, self.nodes
curr = nodes[key]
if curr.cnt == 1:
nodes.pop(key)
else:
prev = curr.prev
if prev == root or prev.cnt < curr.cnt - 1:
nodes[key] = prev.insert(Node(key, curr.cnt - 1))
else:
prev.keys.add(key)
nodes[key] = prev
curr.keys.discard(key)
if not curr.keys:
curr.remove()
def getMaxKey(self) -> str:
return next(iter(self.root.prev.keys))
def getMinKey(self) -> str:
return next(iter(self.root.next.keys))
# Your AllOne object will be instantiated and called as such:
# obj = AllOne()
# obj.inc(key)
# obj.dec(key)
# param_3 = obj.getMaxKey()
# param_4 = obj.getMinKey()
|
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
96
97
98
99
| class AllOne {
Node root = new Node();
Map<String, Node> nodes = new HashMap<>();
public AllOne() {
root.next = root;
root.prev = root;
}
public void inc(String key) {
if (!nodes.containsKey(key)) {
if (root.next == root || root.next.cnt > 1) {
nodes.put(key, root.insert(new Node(key, 1)));
} else {
root.next.keys.add(key);
nodes.put(key, root.next);
}
} else {
Node curr = nodes.get(key);
Node next = curr.next;
if (next == root || next.cnt > curr.cnt + 1) {
nodes.put(key, curr.insert(new Node(key, curr.cnt + 1)));
} else {
next.keys.add(key);
nodes.put(key, next);
}
curr.keys.remove(key);
if (curr.keys.isEmpty()) {
curr.remove();
}
}
}
public void dec(String key) {
Node curr = nodes.get(key);
if (curr.cnt == 1) {
nodes.remove(key);
} else {
Node prev = curr.prev;
if (prev == root || prev.cnt < curr.cnt - 1) {
nodes.put(key, prev.insert(new Node(key, curr.cnt - 1)));
} else {
prev.keys.add(key);
nodes.put(key, prev);
}
}
curr.keys.remove(key);
if (curr.keys.isEmpty()) {
curr.remove();
}
}
public String getMaxKey() {
return root.prev.keys.iterator().next();
}
public String getMinKey() {
return root.next.keys.iterator().next();
}
}
class Node {
Node prev;
Node next;
int cnt;
Set<String> keys = new HashSet<>();
public Node() {
this("", 0);
}
public Node(String key, int cnt) {
this.cnt = cnt;
keys.add(key);
}
public Node insert(Node node) {
node.prev = this;
node.next = this.next;
node.prev.next = node;
node.next.prev = node;
return node;
}
public void remove() {
this.prev.next = this.next;
this.next.prev = this.prev;
}
}
/**
* 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();
*/
|
