Untitled
unknown
c_cpp
13 days ago
2.5 kB
9
Indexable
#include <unordered_map> #include <unordered_set> #include <list> #include <string> using namespace std; class AllOne { public: AllOne() {} void inc(string key) { // If key is new, place it in the 0-count bucket (create if necessary) if (keyToBucket.find(key) == keyToBucket.end()) { if (buckets.empty() || buckets.front().count != 0) { buckets.push_front({0, {}}); } buckets.front().keys.insert(key); keyToBucket[key] = buckets.begin(); } auto currentBucket = keyToBucket[key]; auto nextBucket = next(currentBucket); // Check if a bucket with count+1 exists, else create it if (nextBucket == buckets.end() || nextBucket->count > currentBucket->count + 1) { nextBucket = buckets.insert(nextBucket, {currentBucket->count + 1, {}}); } // Move key to next bucket nextBucket->keys.insert(key); keyToBucket[key] = nextBucket; // Remove key from current bucket and delete bucket if empty currentBucket->keys.erase(key); if (currentBucket->keys.empty()) { buckets.erase(currentBucket); } } void dec(string key) { if (keyToBucket.find(key) == keyToBucket.end()) return; auto currentBucket = keyToBucket[key]; int newCount = currentBucket->count - 1; // If new count is not zero, move to prev bucket if (newCount > 0) { auto prevBucket = (currentBucket == buckets.begin()) ? buckets.end() : prev(currentBucket); if (currentBucket == buckets.begin() || prevBucket->count < newCount) { prevBucket = buckets.insert(currentBucket, {newCount, {}}); } prevBucket->keys.insert(key); keyToBucket[key] = prevBucket; } else { keyToBucket.erase(key); // Remove key entirely } // Remove key from current bucket and delete bucket if empty currentBucket->keys.erase(key); if (currentBucket->keys.empty()) { buckets.erase(currentBucket); } } string getMaxKey() const { return buckets.empty() ? "" : *(buckets.back().keys.begin()); } string getMinKey() const { return buckets.empty() ? "" : *(buckets.front().keys.begin()); } private: struct Bucket { int count; unordered_set<string> keys; }; list<Bucket> buckets; unordered_map<string, list<Bucket>::iterator> keyToBucket; };
Editor is loading...
Leave a Comment