Why using a single unordered_set will give TLE? (c++)


  • 1

    I was thinking why this problem is ranked Medium while it seems a unordered_set can solve it all, then I got TLE...
    Can anyone take a look? To me it seems all operations should be O(1), only suspects will be:

            int ret = *numbers.begin(); // should be O(1), right?
            numbers.erase(numbers.begin()); // should be O(1), right? or it went into the worst case O(N)? how?
    

    Full code is as below:

    class PhoneDirectory {
        unordered_set<int> numbers;
    public:
        /** Initialize your data structure here
            @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
        PhoneDirectory(int maxNumbers) {
            for (int i = 0; i < maxNumbers; ++ i)
                numbers.insert(i);
        }
        
        /** Provide a number which is not assigned to anyone.
            @return - Return an available number. Return -1 if none is available. */
        int get() {
            if (numbers.empty())
                return -1;
                
            int ret = *numbers.begin(); // should be O(1), right?
            numbers.erase(numbers.begin()); // should be O(1), right?
            return ret;
        }
        
        /** Check if a number is available or not. */
        bool check(int number) {
            return numbers.find(number) != numbers.end();
        }
        
        /** Recycle or release a number. */
        void release(int number) {
            numbers.insert(number);
        }
    };
    

  • 0
    F

    I think for the initialization part, because you insert the element one by one. That will cause the set to be dynamically reallocate several times. Maybe that is the problem.


  • 0

    @for_the_glory Still doesn't make too much sense to me, if unordered_set is such inefficient, it basically means we could not use unordered_set in practice, but I guess it's being used everywhere...


  • 0
    P

    Actually, now it can pass


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.