One question about random function (cpp)


  • 0
    P

    Here is my code:

    typedef long long LL;
    const LL N = 1000000007; 
    class RandomizedSet {
        unordered_map<int,int> index;
        vector<int> vals;
        LL count;
    public:
        /** Initialize your data structure here. */
        RandomizedSet() {
            count = 0;
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        bool insert(int val) {
            if(index.find(val)!=index.end()) return false;
            index[val] = vals.size();
            vals.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(index.find(val)==index.end()) return false;
            vals[index[val]] = vals[vals.size()-1];
            index[vals[vals.size()-1]] = index[val];
            vals.pop_back();
            index.erase(val);
            return true;
        }
        
        /** Get a random element from the set. */
        int getRandom() {
            if(vals.empty()) return 0;
            count++;
            //return vals[(count*N)%vals.size()]; //(1) why this one can not pass
            return vals[rand()%vals.size()]; //(2) This one passes
        }
    };
    
    /**
     * Your RandomizedSet object will be instantiated and called as such:
     * RandomizedSet obj = new RandomizedSet();
     * bool param_1 = obj.insert(val);
     * bool param_2 = obj.remove(val);
     * int param_3 = obj.getRandom();
     */
    

    First, I defined a random function by myself to determine the index of the return val: simply "count*N%vals.size()" and N = 1000000007, which is a big prime number. After each calling of getRandom(), count++. However, the code fails at one case: initially insert four values: "1,10,20,30", and keep calling getRandom repetitively. (I thought my code should work, since all four numbers have the same probability to be chosen.)
    Then I use "rand()%vals.size()", it passed all the cases.


Log in to reply
 

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