Best & simple c++ using map & vector beats 96.48% 48ms


  • 0
    C

    class RandomizedCollection {
    public:
    RandomizedCollection() {
    }

    bool insert(int val) {
        set.push_back(val);
        map[val].push_back(set.size() - 1);
        if(map[val].size() != 1) return false;
        else return true;
    }
    
    bool remove(int val) {
        if(map.find(val) == map.end() || map[val].size() == 0) return false;
        set[map[val].back()] = set.back();
        *find(map[set.back()].begin(), map[set.back()].end(), set.size() - 1) = map[val].back();
        set.pop_back();
        map[val].pop_back();
        return true;
    }
    
    int getRandom() {
        return set[rand() % set.size()];
    }
    

    private:
    unordered_map <int, vector<int>> map;
    vector<int> set;
    };


  • 0
    N

    A little change.

    bool insert(int val) {
        map[val].push_back(set.size());
        set.push_back(val);
        return map[val].size() == 1;
    }
    

Log in to reply
 

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