Leetcode #380 | #Medium | [[Хэш-таблицы]] | [[Математика]] | [[Design]]
## Идея
HashMap + ArrayList в листе храним значения, в мапе значение: индекс_в_листе, для удаления свопаем элемент в листе с последним и удаляем за O(1), попутно обновляем мапу  
Random random = new Random(); int rand = random.nextInt(size); <- для рандома
## [[Big-O]]
- Время ```O(1)```
- Память  ```O(N)```
## Код
```Java
class RandomizedSet {
    private List<Integer> list = new ArrayList<>();
    private Map<Integer, Integer> map = new HashMap<>();
    private Random rand = new Random();

    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int index = map.get(val);
        int lastVal = list.get(list.size() - 1);
        list.set(index, lastVal);
        map.put(lastVal, index);
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}
```