LeetCode 380. Insert Delete GetRandom O(1) 常数时间插入、删除和获取随机元素(C++/Java)

silentteller 2020-01-31 原文

题目：

Design a data structure that supports all following operations in averageO(1) time.

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

分析：

设计一个数据结构支持以下几个操作。

insert(val): 当元素 val 不存在时，向集合中插入该项。
remove(val): 元素 val 存在时，从集合中移除该项。
getRandom: 随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

我们使用HashMap来支持插入和移除操作，利用数组来支持对数据的随机访问。插入元素时，将val和该val在数组中索引值存入map中，新插入的元素实际上在数组中的索引就是数组还有元素的个数，将元素加到动态数组的尾端。

移除元素时，为了能够达到O(1)，除了将val在map中移除，还要对数组进行操作，如果单纯的将val所对应的索引处的元素删除，由于后续的所有元素都要向前移动，这样会浪费大量的时间。我们知道数组移除最后一个元素的时间复杂度时O(1)，我们将要移除的元素和数组的最后一个元素交换，也可以将最后一个元素覆盖到要移除元素的位置，同时修改最后一个元素在map中对应的索引，最后删除掉数组最后一个元素，就可以保证常数时间的移除操作。最后在数组大小的范围内产生随机数，返回对应的元素，即可实现随机访问。

程序:

C++

class RandomizedSet {
public:
    /** Initialize your data structure here. */
    RandomizedSet() {
        
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(m.count(val))
            return false;
        m[val] = v.size();
        v.push_back(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(!m.count(val))
            return false;
        int index = m[val];
        m[v.back()] = index;
        v[index] = v.back();
        m.erase(val);
        v.pop_back();
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        int index = rand() % v.size();
        return v[index];
    }
private:
    unordered_map<int, int> m;
    vector<int> v;
};

Java

class RandomizedSet {

    /** Initialize your data structure here. */
    public RandomizedSet() {
        
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(map.containsKey(val))
            return false;
        map.put(val, list.size());
        list.add(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(!map.containsKey(val))
            return false;
        int index = map.get(val);
        map.put(list.get(list.size()-1), index);
        list.set(index, list.get(list.size()-1));
        list.remove(list.size()-1);
        map.remove(val);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        Random r = new Random();
        return list.get(r.nextInt(list.size()));
    }
    private HashMap<Integer, Integer> map = new HashMap<>();
    private ArrayList<Integer> list = new ArrayList<>();
}