380.Insert Delete GetRandom O(1)
===
###### tags: `Medium`,`Array`,`Hash Table`,`Math`

[380. Insert Delete GetRandom O(1)](https://leetcode.com/problems/insert-delete-getrandom-o1/)

### 題目描述

Implement the `RandomizedSet` class:

* `RandomizedSet()` Initializes the `RandomizedSet` object.
* `bool insert(int val)` Inserts an item `val` into the set if not present. Returns `true` if the item was not present, `false` otherwise.
* `bool remove(int val)` Removes an item `val` from the set if present. Returns `true` if the item was present, `false` otherwise.
* `int getRandom()` Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the **same probability** of being returned.

You must implement the functions of the class such that each function works in **average** $O(1)$ time complexity.

### 範例

**Example 1:**

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); 
// Inserts 1 to the set. Returns true as 1 was inserted successfully.

randomizedSet.remove(2); 
// Returns false as 2 does not exist in the set.

randomizedSet.insert(2); 
// Inserts 2 to the set, returns true. Set now contains [1,2].

randomizedSet.getRandom(); 
// getRandom() should return either 1 or 2 randomly.

randomizedSet.remove(1); 
// Removes 1 from the set, returns true. Set now contains [2].

randomizedSet.insert(2); 
// 2 was already in the set, so return false.

randomizedSet.getRandom(); 
// Since 2 is the only number in the set, getRandom() will always return 2.

**Constraints**:

* $-2^{31}$ <= `val` <= $2^{31} - 1$
* At most $2 * 10^5$ calls will be made to `insert`, `remove`, and `getRandom`.
* There will be at least one element in the data structure when `getRandom` is called.

### 解答

#### Python

from random import randint
class RandomizedSet:

    def __init__(self):
        self.ht = defaultdict(bool)
        self.set = set()

    def insert(self, val: int) -> bool:
        if not self.ht[val]:
            self.ht[val] = True
            self.set.add(val)
            return True
        return False
    
    def remove(self, val: int) -> bool:
        if self.ht[val]:
            self.ht[val] = False
            self.set.remove(val)
            return True
        return False

    def getRandom(self) -> int:
        choose = randint(0, len(self.set) - 1)
        return list(self.set)[choose]

# 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()

> [name=Kobe][time=Tue, Nov 29]

class RandomizedSet:

    def __init__(self):
        self.data = set()

    def insert(self, val: int) -> bool:
        if val in self.data:
            return False
        self.data.add(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.data:
            return False
        self.data.remove(val)
        return True

    def getRandom(self) -> int:
        return sample(self.data, 1)[0]

> [name=Yen-Chi Chen][time=Tue, Nov 29, 2022]

#### C++

class RandomizedSet {
    vector<int> data;
    unordered_map<int, int> m;
public:
    RandomizedSet() {
        
    }
    
    bool insert(int val) {
        if (m.find(val) != m.end()) {
            return false;
        }
        m[val] = data.size();
        data.push_back(val);
        return true;
    }
    
    bool remove(int val) {
        if (m.find(val) != m.end()) {
            data[m[val]] = data.back();
            m[data.back()] = m[val];
            data.pop_back();
            m.erase(val);
            return true;
        }
        return false;
    }
    
    int getRandom() {
        return data[rand() % data.size()];
    }
};

> [name=Yen-Chi Chen][time=Tue, Nov 29, 2022]

#### Javascript

class RandomizedSet {
  constructor() {
    this.map = new Map();
    this.list = [];
  }

  insert(val) {
    if (this.map.has(val)) return false;
    this.map.set(val, this.list.length);
    this.list.push(val);
    return true;
  }

  remove(val) {
    if (!this.map.has(val)) return false;
    const index = this.map.get(val);
    const last = this.list.pop();
    if (index !== this.list.length) {
      this.list[index] = last;
      this.map.set(last, index);
    }
    this.map.delete(val);
    return true;
  }

  getRandom() {
    return this.list[~~(Math.random() * this.list.length)];
  }
}

> [name=Marsgoat][time=Nov 29, 2022]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)