381. Insert Delete GetRandom O(1) - Duplicates allowed

• 381. Insert Delete GetRandom O(1) - Duplicates allowed
  • Description
  • Intuition
  • Pitfall
  • Solution

Description

Here

Intuition

Pitfall

这题目容易跪在以下的solution

public class RandomizedCollection {

  // 不可以用List，很难保最大的就是结尾
  private final Map<Integer, List<Integer>> valToIndex = new HashMap<>();
  private final List<Integer> vals = new ArrayList<>();
  private final Random rand = new Random();

  /**
   * Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
   */
  public boolean insert(int val) {
    final List<Integer> prevSet = valToIndex.putIfAbsent(val, new ArrayList<>());
    valToIndex.get(val).add(vals.size());
    vals.add(val);
    return prevSet == null;
  }

  /**
   * Removes a value from the collection. Returns true if the collection contained the specified element.
   */
  public boolean remove(int val) {
    if (!valToIndex.containsKey(val)) {
      return false;
    }
    final List<Integer> curList = valToIndex.get(val);
    final int toRemoveIndex = curList.remove(curList.size() - 1);
    if (curList.isEmpty()) {
      valToIndex.remove(val);
    }

    if (toRemoveIndex == vals.size() - 1) {
      vals.remove(toRemoveIndex);
      return true;
    }
    final int lastValIndex = vals.size() - 1, lastVal = vals.get(lastValIndex);
    final List<Integer> lastValIndexList = valToIndex.get(lastVal);
    lastValIndexList.set(lastValIndexList.size() - 1, toRemoveIndex);
    swap(vals, toRemoveIndex, lastValIndex);
    vals.remove(lastValIndex);
    return true;
  }

  private static void swap(final List<Integer> list, int i, int j) {
    System.out.println(list + " " + i + " " + j);
    final int tmp = list.get(i);
    list.set(i, list.get(j));
    list.set(j, tmp);
  }

  /**
   * Get a random element from the collection.
   */
  public int getRandom() {
    return vals.get(rand.nextInt(vals.size()));
  }

假设有以下的test case

//["RandomizedCollection","insert","insert","insert","insert","insert","insert","remove","remove","remove","remove",
//[                     [],[10],    [10],     [20],   [20],     [30],   [30],   [10],     [10],     [30],   [30],

当完成所有insert之后，

valToIndex {
    10 -> {0, 1},
    20 -> {2, 3},
    30 -> {4, 5}
}

| i    | 0   | 1   | 2   | 3   | 4   | 5   |
| ---- | --- | --- | --- | --- | --- | --- |
| vals | 10  | 10  | 20  | 20  | 30  | 30  |

After the first remove(10)

valToIndex {
    10 -> {0},
    20 -> {2, 3},
    30 -> {4, 1}
}

| i    | 0   | 1   | 2   | 3   | 4   |
| ---- | --- | --- | --- | --- | --- |
| vals | 10  | 30  | 20  | 20  | 30  |

当你试图获取lastVal的lastValIndex的时候，得到的是1，预期是4

Solution