LeetCode Solutions

			

struct Item {
  int val;
  int indexInMap;
  Item(int val, int indexInMap) : val(val), indexInMap(indexInMap) {}
};

class RandomizedCollection {
 public:
  /** Inserts a value to the collection. Returns true if the collection did not
   * already contain the specified element. */
  bool insert(int val) {
    valToIndices[val].push_back(items.size());
    items.emplace_back(val, valToIndices[val].size() - 1);
    return valToIndices[val].size() == 1;
  }

  /** Removes a value from the collection. Returns true if the collection
   * contained the specified element. */
  bool remove(int val) {
    if (!valToIndices.count(val))
      return false;

    const int index = valToIndices[val].back();
    valToIndices[items.back().val][items.back().indexInMap] = index;
    valToIndices[val].pop_back();
    if (valToIndices[val].empty())
      valToIndices.erase(val);
    items[index] = items.back();
    items.pop_back();
    return true;
  }

  /** Get a random element from the collection. */
  int getRandom() {
    const int index = rand() % items.size();
    return items[index].val;
  }

 private:
  unordered_map<int, vector<int>> valToIndices;
  vector<Item> items;
};

			

class Item {
  public int val;
  public int indexInMap;
  public Item(int val, int indexInMap) {
    this.val = val;
    this.indexInMap = indexInMap;
  }
}

class RandomizedCollection {
  /**
   * Inserts a value to the collection. Returns true if the collection did not already contain the
   * specified element.
   */
  public boolean insert(int val) {
    valToIndices.putIfAbsent(val, new ArrayList<>());
    valToIndices.get(val).add(items.size());
    items.add(new Item(val, valToIndices.get(val).size() - 1));
    return valToIndices.get(val).size() == 1;
  }

  /**
   * Removes a value from the collection. Returns true if the collection contained the specified
   * element.
   */
  public boolean remove(int val) {
    if (!valToIndices.containsKey(val))
      return false;

    final int index = lastIndex(valToIndices.get(val));
    valToIndices.get(last(items).val).set(last(items).indexInMap, index);
    final int indicesSize = valToIndices.get(val).size();
    valToIndices.get(val).remove(indicesSize - 1);
    if (valToIndices.get(val).isEmpty())
      valToIndices.remove(val);
    items.set(index, last(items));
    items.remove(items.size() - 1);
    return true;
  }

  /** Get a random element from the collection. */
  public int getRandom() {
    final int index = rand.nextInt(items.size());
    return items.get(index).val;
  }

  private Map<Integer, List<Integer>> valToIndices = new HashMap<>();
  private List<Item> items = new ArrayList<>();
  private Random rand = new Random();

  private int lastIndex(List<Integer> indices) {
    return indices.get(indices.size() - 1);
  }

  private Item last(List<Item> items) {
    return items.get(items.size() - 1);
  }
}

			

class RandomizedCollection:
  def __init__(self):
    """
    Initialize your data structure here.
    """
    self.vals = []
    self.valToIndices = defaultdict(list)

  def insert(self, val: int) -> bool:
    """
    Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
    """
    self.valToIndices[val].append(len(self.vals))
    self.vals.append([val, len(self.valToIndices[val]) - 1])
    return len(self.valToIndices[val]) == 1

  def remove(self, val: int) -> bool:
    """
    Removes a value from the collection. Returns true if the collection contained the specified element.
    """
    if val not in self.valToIndices or self.valToIndices[val] == []:
      return False

    index = self.valToIndices[val][-1]
    self.valToIndices[self.vals[-1][0]][self.vals[-1][1]] = index
    self.valToIndices[val].pop()
    self.vals[index] = self.vals[-1]
    self.vals.pop()
    return True

  def getRandom(self) -> int:
    """
    Get a random element from the collection.
    """
    index = randint(0, len(self.vals) - 1)
    return self.vals[index][0]