Leetcode.380.Insert Delete GetRa

题目

设计一个数据结构,实现插入,删除,取随机值,要求时间复杂度为O(1).

思路

插入和删除使用map,主要是取随机值,最好是有一个数组记录map的索引,但是数组的删除比较慢,只能删除最后一个,所以在删除时进行内容交换.

class RandomizedSet {
private:
    unordered_map<int,int> m_map;
    vector<int> m_vec;
public:
    /** Initialize your data structure here. */
    RandomizedSet() {
        srand((unsigned)time(NULL));
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if (m_map.count(val) > 0) {
            return false;
        }
        m_vec.push_back(val);
        m_map[val] = (int)m_vec.size()-1;
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if (m_map.count(val) == 0) {
            return false;
        }
        int index = m_map[val];
        int last = (int)m_vec.size()-1;
        int temp = m_vec[m_vec.size()-1];
        m_vec[last] = m_vec[index];
        m_vec[index] = temp;
        m_map[temp] = index;
        m_map[val] = last;
        m_vec.pop_back();
        m_map.erase(val);
        return true;
    }

    /** Get a random element from the set. */
    int getRandom() {
        int res = (rand() % (m_vec.size()));
        return m_vec[res];
    }
};

总结

灵活运算数组, 数组虽然插入删除比较慢,但是可以通过交换数组内容来快速删除插入.

还可以使用set,或者将map转换为数组来取随机值,但是效率太低.