【leetcode】 381 Insert Delete GetRandom O(1) - Duplicates allowed

建立数据结构 O(1)

描述

建立一个数据结构，对以下操作都是O(1)时间：
ss.insert(val)
ss.remove(val)
ss.getRandom()

思路

vector 完成一切。嗯，下面是效果图

😆😆😆😆😆😆
vector 随机访问很方便，但是查找元素进行删除就不是那么方便了，map 能快速查找，很方便。

代码

class RandomizedCollection {
public:
    /** 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) {
        bool flag = false;
        int index = find(nums.begin(), nums.end(), val) - nums.begin();
        if (index >= nums.size()) {
            flag = true;;
        }
        nums.push_back(val);
        return flag;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        int index = find(nums.begin(), nums.end(), val)-nums.begin();
        if (index >= nums.size()) {
            return false;
        }
        nums.erase(index+nums.begin());
        return true;
    }

    /** Get a random element from the collection. */
    int getRandom() {
        static default_random_engine e(time(0));
        uniform_int_distribution<int> u(0,nums.size()-1);
        return nums[u(e)];
    }

private:
    vector<int> nums;
};

别人的代码

class RandomizedCollection {
public:
    /** Initialize your data structure here. */
    RandomizedCollection() {
        srand(time(NULL));
    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    bool insert(int val) {
        data.push_back(val);
        valpos[val].insert( data.size() - 1 );
        return (valpos[val].size() == 1);
    }

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

        //same idea with non-duplication version, but need be careful with some edge case
        int _idx = *(valpos[val].begin());
        int _val = data.back();

        valpos[_val].insert(_idx);
        data[_idx] = _val;

        valpos[val].erase(_idx);
        if (valpos[val].size()==0){
            valpos.erase(val);
        }

        data.pop_back();
        if ( _idx < data.size() ){
            valpos[_val].erase(data.size());
            valpos[_val].insert(_idx);
        }
                return true;
    }

    /** Get a random element from the collection. */
    int getRandom() {
        return data[ rand() % data.size() ];
    }
private:
    unordered_map<int, unordered_set<int>> valpos; //value position map
    vector<int> data;
    bool find(int val) {
        return (valpos.find(val) != valpos.end());
    }
};

参考

原题链接
参考链接

---