Problem
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.
Note
Use DoublyLinkedList to get max/min key (max/min count)
We put max count Bucket at tail, min count Bucket at head, O(1)
So the node(Bucket) must contain count property
And we can use map to access each node in O(1)
Each Bucket could have multiple keys of same count, so use Set to store keys
To get count of a key, use Map to achieve O(1)
Solution
class AllOne {
private class Bucket {
int count;
Set keySet;
Bucket prev;
Bucket next;
public Bucket(int count) {
this.count = count;
this.keySet = new HashSet<>();
}
}
private Bucket head;
private Bucket tail;
private Map countBucketMap;
private Map keyCountMap;
public AllOne() {
head = new Bucket(Integer.MIN_VALUE);
tail = new Bucket(Integer.MAX_VALUE);
head.next = tail;
tail.prev = head;
countBucketMap = new HashMap<>();
keyCountMap = new HashMap<>();
}
public void inc(String key) {
if (keyCountMap.containsKey(key)) {
//existing key
updateKey(key, 1);
} else {
//new key
keyCountMap.put(key, 1);
if (head.next.count != 1) {
addBucketAfter(head, new Bucket(1));
}
head.next.keySet.add(key);
countBucketMap.put(1, head.next);
}
}
public void dec(String key) {
if (keyCountMap.containsKey(key)) {
int count = keyCountMap.get(key);
if (count == 1) {
keyCountMap.remove(key);
removeKeyFromBucket(countBucketMap.get(count), key);
} else {
updateKey(key, -1);
}
}
}
private void updateKey(String key, int i) {
int count = keyCountMap.get(key);
keyCountMap.put(key, count+i);
Bucket pre = countBucketMap.get(count);
Bucket cur;
if (countBucketMap.containsKey(count+i)) {
cur = countBucketMap.get(count+i);
} else {
cur = new Bucket(count+i);
countBucketMap.put(count+i, cur);
if (i == 1) {
addBucketAfter(pre, cur);
} else {
addBucketAfter(pre.prev, cur);
}
}
cur.keySet.add(key);
removeKeyFromBucket(pre, key);
}
private void addBucketAfter(Bucket pre, Bucket cur) {
Bucket next = pre.next;
pre.next = cur;
cur.prev = pre;
cur.next = next;
next.prev = cur;
}
private void removeKeyFromBucket(Bucket bucket, String key) {
bucket.keySet.remove(key);
if (bucket.keySet.size() == 0) {
bucket.prev.next = bucket.next;
bucket.next.prev = bucket.prev;
bucket.prev = null;
bucket.next = null;
countBucketMap.remove(bucket.count);
}
}
public String getMaxKey() {
return tail.prev == head ? "" : (String) tail.prev.keySet.iterator().next();
}
public String getMinKey() {
return head.next == tail ? "" : (String) head.next.keySet.iterator().next();
}
}
Reference: https://leetcode.com/problems...
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/72309.html
