Untitled

 avatar
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