C++_vector + map_82ms_98.40%_Accepted!


  • 0
    class RandomizedCollection {
    vector<int> nums;
    unordered_map<int, vector<int>> myMap;
    public:
    /** Initialize your data structure here. */
    RandomizedCollection() {
        //nums.clear();
        //myMap.clear();
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already the specified element. */
    
    bool insert(int val) {
        if(myMap.find(val) == myMap.end()){
            nums.push_back(val);
            myMap[val].push_back(nums.size()-1);
            return true;
        }else{
            nums.push_back(val);
            myMap[val].push_back(nums.size()-1);
            return false;}
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        if(myMap.find(val) == myMap.end()){return false;}
        
        int index_val = myMap[val].back();
        myMap[val].pop_back();
        if(myMap[val].size() == 0){myMap.erase(val);}
        
        int num_last = nums[nums.size()-1];
        if(num_last != val){
            nums[index_val] = num_last;
            myMap[num_last].pop_back();
            myMap[num_last].push_back(index_val);
            sort(myMap[num_last].begin(), myMap[num_last].end());// to make sure the largest rank is at the end of the vector
        }
        nums.pop_back();
        return true;
    }
    
    /** Get a random element from the collection. */
    int getRandom() {
        int ans = nums[rand()%nums.size()];
        return ans;
    }
    };
    

    0_1476062733727_c++.png


  • 0
    Q

    you used sort() . How could this be O(1) ?


Log in to reply
 

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