-
Notifications
You must be signed in to change notification settings - Fork 2
/
AllOOneDataStructure.java
80 lines (67 loc) · 1.75 KB
/
AllOOneDataStructure.java
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
package com.algorithm.playground.leetcode.problems.lc400.lc430.lc432;
import java.util.*;
/**
* https://leetcode.com/problems/all-oone-data-structure/description/
*/
public class AllOOneDataStructure {
class AllOne {
private Map<String, Integer> counts = new HashMap<>();
private TreeMap<Integer, Set<String>> strings = new TreeMap<>();
/**
* Initialize your data structure here.
*/
public AllOne() { }
/**
* Inserts a new key <Key> with value 1. Or increments an existing key by 1.
*/
public void inc(String key) {
updateCount(key, getCountForUpdate(key) + 1);
}
/**
* Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
*/
public void dec(String key) {
updateCount(key, getCountForUpdate(key) - 1);
}
/**
* Returns one of the keys with maximal value.
*/
public String getMaxKey() {
return getAnyForKey(strings.isEmpty() ? 0 : strings.lastKey());
}
/**
* Returns one of the keys with Minimal value.
*/
public String getMinKey() {
return getAnyForKey(strings.isEmpty() ? 0 : strings.firstKey());
}
private int getCountForUpdate(String key) {
int curr = counts.getOrDefault(key, 0);
if (strings.containsKey(curr)) {
Set<String> set = strings.get(curr);
set.remove(key);
if (set.isEmpty()) {
strings.remove(curr);
}
}
return curr;
}
private void updateCount(String key, int count) {
if (count <= 0) {
counts.remove(key);
} else {
counts.put(key, count);
if (!strings.containsKey(count)) {
strings.put(count, new HashSet<>());
}
strings.get(count).add(key);
}
}
private String getAnyForKey(int key) {
if (key == 0) {
return "";
}
return strings.get(key).iterator().next();
}
}
}