381. Insert/Del GetRandom O(1)-Duplicates allowed

实现O(1)时间插入和删除以及随机获取一个数，并且要求根据数字个数返回随机值，数目多的概率更高。由于允许重复，要把所有出现过的数即使重复也都要存下来(vals)，这样才能保证rand()/vals.size()时把数目也考虑了进去。查随机值用rand()/vals.size()，要在不改变vals数目基础上实现删除，只能把要删除的元素和当前最后的元素做swap。而且要求O(1)添和删，因此要用hash map存，还要把val在vals的所有位置都存下来。对要删除的元素正好是最后一个元素时把元素的值从map中删除，或者vals每个元素再存下自己是第几个val，以方便快速在indices中定位。

/*
 * @lc app=leetcode id=381 lang=cpp
 *
 * [381] Insert Delete GetRandom O(1) - Duplicates allowed
 *
 * https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/description/
 *
 * algorithms
 * Hard (32.47%)
 * Likes:    511
 * Dislikes: 52
 * Total Accepted:    48.9K
 * Total Submissions: 149K
 * Testcase Example:  '["RandomizedCollection","insert","insert","insert","getRandom","remove","getRandom"]\n[[],[1],[1],[2],[],[1],[]]'
 *
 * Design a data structure that supports all following operations in average
 * O(1) time.
 * Note: Duplicate elements are allowed.
 * 
 * 
 * insert(val): Inserts an item val to the collection.
 * remove(val): Removes an item val from the collection if present.
 * getRandom: Returns a random element from current collection of elements. The
 * probability of each element being returned is linearly related to the number
 * of same value the collection contains.
 * 
 * 
 * 
 * Example:
 * 
 * // Init an empty collection.
 * RandomizedCollection collection = new RandomizedCollection();
 * 
 * // Inserts 1 to the collection. Returns true as the collection did not
 * contain 1.
 * collection.insert(1);
 * 
 * // Inserts another 1 to the collection. Returns false as the collection
 * contained 1. Collection now contains [1,1].
 * collection.insert(1);
 * 
 * // Inserts 2 to the collection, returns true. Collection now contains
 * [1,1,2].
 * collection.insert(2);
 * 
 * // getRandom should return 1 with the probability 2/3, and returns 2 with
 * the probability 1/3.
 * collection.getRandom();
 * 
 * // Removes 1 from the collection, returns true. Collection now contains
 * [1,2].
 * collection.remove(1);
 * 
 * // getRandom should return 1 and 2 both equally likely.
 * collection.getRandom();
 * 
 * 
 */

// @lc code=start
class RandomizedCollection {
public:
    // <val, index in the index array>
    vector<int> vals;
    // val-> index array: indice in vals
    unordered_map<int, unordered_set<int>> m;
    /** Initialize your data structure here. */
    RandomizedCollection() {}
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    bool insert(int val) {
        m[val].insert(vals.size());
        vals.push_back(val);
        return m[val].size() == 1;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        if (!m.count(val)) return false;
        const auto last = vals.back();
        if (val == last) {
            vals.pop_back();
            m[val].erase(vals.size());
            if (m[val].empty()) m.erase(val);
            return true;
        }
        int ind_to_del = *m[val].begin();
        // 把最后一个元素交换到被rm的地方去
        // 更新最后一个元素的index成rm的index
        m[last].erase(vals.size() - 1);
        m[last].insert(ind_to_del);
        // swap
        swap(vals.back(), vals[ind_to_del]);
        // 删除被rm的元素
        vals.pop_back();
        m[val].erase(ind_to_del);
        if (m[val].empty()) m.erase(val);
        return true;
    }
    
    /** Get a random element from the collection. */
    int getRandom() {
        return vals[rand() % vals.size()];
    }
};

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection* obj = new RandomizedCollection();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */
// @lc code=end