LeetCode

381. O(1) 时间插入、删除和获取随机元素 - 允许重复

常数时间的插入容易想到链表和数组，常数时间的删除容易想到哈希表，元素被返回的概率与这个元素的数量有关意味着必须要能统计这个元素出现的次数，容易想到哈希表。注意是平均情况下的复杂度
删除的情况写起来容易出错，面试的时候需要额外注意。

  1. class RandomizedCollection {
  2.     int size = 0;
  3.     int[] values;
  4.     Map<Integer, Set<Integer>> positions;
  5.     Random rdm;
  6.     public RandomizedCollection() {
  7.         values = new int[1024];
  8.         positions = new HashMap();
  9.         rdm = new Random();
  10.     }
  12.     public boolean insert(int val) {
  13.         if (size == values.length) {
  14.             values = Arrays.copyOf(values, size << 1);
  15.         }
  16.         Set<Integer> position = positions.getOrDefault(val, new HashSet<Integer>());
  17.         position.add(size);
  18.         positions.put(val, position);
  19.         values[size++] = val;
  20.         return position.size() == 1 ? true : false;
  21.     }
  23.     public boolean remove(int val) {
  24.         if (positions.getOrDefault(val, new HashSet<Integer>()).size() == 0) return false;
  25.         for (int pos : positions.get(val)) {
  26.             delete(pos);
  27.             break;
  28.         }
  29.         return true;
  30.     }
  31.     private void delete(int position) {
  32.         int deleteVal = values[position], lastPositionVal = values[size-1];
  33.         if (deleteVal != lastPositionVal) {
  34.             values[position] = lastPositionVal;
  35.             positions.get(lastPositionVal).remove(size-1);
  36.             positions.get(lastPositionVal).add(position);
  37.             positions.get(deleteVal).remove(position);
  38.         } else {
  39.             positions.get(deleteVal).remove(size-1);
  40.         }
  41.         size--;
  42.     }
  44.     public int getRandom() {
  45.         if (size == 0)  return -1;
  46.         return values[rdm.nextInt(size)];
  47.     }
  48. }