class AllOne {
public:
/** Initialize your data structure here. */
AllOne() {
}
/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
void inc(string key) {
if (iters.find(key) == iters.end()) {
if (ones.empty()  ones.begin()>first != 1) ones.insert(ones.begin(), make_pair(1, KeySet()));
ones.begin()>second.insert(key);
iters[key] = ones.begin();
}
else {
Ones::iterator it, next;
it = next = iters[key];
next++;
if (next != ones.end() && next>first == it>first + 1) next>second.insert(key);
else next = ones.insert(next, make_pair(iters[key]>first + 1, KeySet({ key })));
iters[key] = next;
it>second.erase(key);
if (it>second.empty()) ones.erase(it);
}
}
/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
void dec(string key) {
if (iters.find(key) != iters.end()) {
Ones::iterator it, prev;
prev = it = iters[key];
if (it != ones.begin()) prev;
if (it>first != 1) {
if (it == ones.begin()  prev>first != it>first  1)
prev = ones.insert(it, make_pair(iters[key]>first  1, KeySet()));
prev>second.insert(key);
iters[key] = prev;
}
else iters.erase(key);
it>second.erase(key);
if (it>second.empty()) ones.erase(it);
}
}
/** Returns one of the keys with maximal value. */
string getMaxKey() {
return ones.empty() ? "" : *ones.rbegin()>second.begin();
}
/** Returns one of the keys with Minimal value. */
string getMinKey() {
return ones.empty() ? "" : *ones.begin()>second.begin();
}
private:
typedef unordered_set<string> KeySet;
typedef list<pair<int, KeySet>> Ones;
Ones ones;
unordered_map<string, Ones::iterator> iters;
};
C++ O(1) 0ms AC Solution



@Ren.W I see you did some other changes as well. I wrote my own C++ solution yesterday, interesting to see how similar our codes ended up.
Yours is wrong now, though, you fail for example:
Input: ["AllOne","inc","inc","inc","inc","inc","dec","dec","getMaxKey","getMinKey"] [[],["a"],["b"],["b"],["b"],["b"],["b"],["b"],[],[]] Your answer: [null,null,null,null,null,null,null,null,"a","a"]
Max should be "b", because its value is 2 while "a" only has value 1. Problem is that your first
dec
turnsa=1, b=4
intoa=1, b=1
instead ofa=1, b=3
.@1337c0d3r can you add this test case? And fix the C++ judge, because the expected answer is also wrong.


@StefanPochmann
I guess I have fixed the bug :)
Thank you very much for your comments.