Correct and Wrong solutions all passed test.


  • 0
    S

    //Wrong solution

    class RandomizedSet {
    private:
        unordered_set<int> dict;
    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(dict.find(val) != dict.end()) return false;
            else{
                dict.insert(val);
            }
            return true;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            if(dict.find(val) == dict.end()) return false;
            else{
                dict.erase(val);
            }
            return true;
        }
        
        /** Get a random element from the set. */
        int getRandom() {
            int n = rand() % (int)dict.size();
            auto it = dict.begin();
            for(int i = 0; i < n; i++){
                it++;
            }
            return *it;
        }
    };
    
    

    //Correct solution

    class RandomizedSet {
    private:
        vector<int> nums;
        unordered_map<int, int> dict;
    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(dict.find(val) != dict.end()) return false;
            else{
                dict[val] = nums.size();
                nums.push_back(val);
            }
            return true;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            if(dict.find(val) == dict.end()) return false;
            else{
                int last = nums.back();
                int idx = dict[val];
                nums[idx] = last;
                nums.pop_back();
                dict[last] = idx;
                dict.erase(val);
            }
            return true;
        }
        
        /** Get a random element from the set. */
        int getRandom() {
            return nums[rand() % (int)nums.size()];
        }
    };
    

  • 0

    Why do you classify the first solution as wrong?


  • 0

    @babhishek21 Iterator used in the first solution should not be considered as "true randomness" and I think the complexity fails.


  • 0

    @haruhiku What do you mean by true randomness? You are using a system generated random number in both of them. They are equally random.

    For that matter, you can barely ever get true randomness.


  • 0

    @babhishek21 Yeah I know what you mean. I am not very good at maths but using an iterator x.begin() gives me a feeling that the programmer has a preference about which number to start with...Probably I am wrong in some aspects.


  • 0

    @haruhiku said in Correct and Wrong solutions all passed test.:

    gives me a feeling that the programmer has a preference about which number to start with

    That's irrelevant. If I randomly pick a number i from 1 to 26 and you order the letters from A to Z in your favorite order, and then we look at the i-th of your letters, then that's still proper randomness. Doesn't matter what order you choose, as long as my pick and your order aren't somehow related.

    The real reason it's wrong is that it's not O(1).


Log in to reply
 

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