Short C++ using unordered_set, still O(1) right?


  • -1
    F
    class RandomizedSet {
    private:
        unordered_set<int> storage;
    public:
        /** Initialize your data structure here. */
        RandomizedSet() {
            
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        bool insert(int val) {
            if (storage.count(val)) return false;
            storage.insert(val);
            return true;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            if (!storage.count(val)) return false;
            storage.erase(val);
            return true;
        }
        
        /** Get a random element from the set. */
        int getRandom() {
            int i = rand() % storage.size();
            auto it = storage.begin();
            advance(it, i);
            return *it;
        }
    };
    

  • 0
    C

    The getRandom is linear time complexity.When you use andvance() to move the iterator of set,it's implemented by iterator++ or iterator-- for n times.That's because you cannt randomly access element in set.


Log in to reply
 

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