380. Insert Delete GetRandom O(1) - cocoder39/coco39_LC GitHub Wiki

class RandomizedSet:

    def __init__(self):
        self.dict = {}
        self.list = []
        

    def insert(self, val: int) -> bool:
        isPresent = val in self.dict
        if isPresent:
            return False
        
        self.list.append(val)
        self.dict[val] = len(self.list) - 1

        return True
        

    def remove(self, val: int) -> bool:
        isPresent = val in self.dict
        if not isPresent:
            return False
        
        remove_idx = self.dict[val]
        last_idx = len(self.list) - 1
        self.dict[self.list[last_idx]] = remove_idx
        del self.dict[val]
        self.list[remove_idx], self.list[last_idx] = self.list[last_idx], self.list[remove_idx]
        self.list.pop()
        return True
        

    def getRandom(self) -> int:
        return random.choice(self.list)
        


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

class RandomizedSet {
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 (map.find(val) != map.end()) {
            return false;
        } 
        data.push_back(val);
        map[val] = data.size() - 1;
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if (map.find(val) == map.end()) {
            return false;
        } 
        int back = data.back();
        int idx1 = map[val];
        int idx2 = map[back];
        swap(data[idx1], data[idx2]);
        data.resize(data.size() - 1);
        map[back] = map[val];
        map.erase(val);
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        if (! data.empty())
            return data[rand() % data.size()];
        return 0;
    }
private:
    vector<int> data;
    unordered_map<int, int> map; //map[i] = j if data[j] = i
};