Lexi's Leetcode solutions

想random只能用array，insert remove全O(1)只有hashmap，结合一下就可以了。

public class RandomSetStructure {
  Map<Integer, Integer> map;
  List<Integer> array;
  Random random;
  public void insert(int a) {
    if (map.containsKey(a))
      return;
    array.add(a);
    map.put(a, array.size() - 1);
  }
  public void remove(int a) throws Exception{
    if (!map.containsKey(a))
      throw new RuntimeException();
    int index = map.get(a);
    map.remove(a);
    array.set(index, array.get(array.size() - 1));
    map.put(array.get(index), index);
    array.remove(array.size() - 1);
  }
  public int rand() {
    if (map.isEmpty())
      throw new RuntimeException();
    return array.get(random.nextInt(array.size()));
  }
}