432. All O`one Data Structure
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 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 * 104
calls will be made toinc
,dec
,getMaxKey
, andgetMinKey
.
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 |
|
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 |
|