LeetCode380.InsertDeleteGetRandomO(1)思路详解

原题

Design a data structure that supports all following operations in average O(1) time.
1&＃xff0c;insert(val): Inserts an item val to the set if not already present.
2&＃xff0c;remove(val): Removes an item val from the set if present.
3&＃xff0c;getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

题目翻译

设计一个数据结构&＃xff0c;该数据可以在O(1)时间内完成以下操作&＃xff1a;
1&＃xff0c;insert(val)&＃xff1a;插入一个元素到集合中&＃xff0c;如果元素之前不存在。
2&＃xff0c;remove(val)&＃xff1a;如果val在集合中存在&＃xff0c;则删除
3&＃xff0c;getRandom&＃xff1a;返回当前集合中随机的一个数。每个元素返回的概率相同。

思路解析

由于题目要求删除和插入的时间复杂度均为O(1)。首先想到使用数组保存所有数据。这样的话&＃xff0c;插入时间复杂度为O(n)。但是删除数据的时间复杂度为O(n)。随机返回操作时间复杂度为O(n)。如何实现O(1)。我们使用一个map来保存数据-位置关系。然后使用vector来保存元素。
1&＃xff0c;insert操作。首先判断val在map中是否存在&＃xff0c;时间复杂度为O(1)。如果存在&＃xff0c;则返回false。否则&＃xff0c;将数据插入到vector中。然后在map中保存数据-位置键值对。时间复杂度为O(1)

2&＃xff0c;remove操作。首先判断val在map中是否存在&＃xff0c;时间复杂度为O(1)。如果不存在&＃xff0c;则返回false。否则&＃xff0c;首先将val的所在位置保存vector尾部元素的值。修改尾部数据的在map中的位置映射。以及val的位置映射。然后删除val在map中映射关系。然后删除vector中最后一个元素。此时时间负责度为O(1)

3&＃xff0c;getRandom操作。有rand()函数产生随机的位置pos。然后返回vector中pos处的元素即可

代码

class RandomizedSet {
public:map data_map; //数字 - 对应位置vector data;/** 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(data_map.count(val) !&＃61; 0){return false;}else{data.push_back(val); //在数组中插入该值data_map[val] &＃61; data.size()-1; //在map中加入该值和数组中的位置对应return true;}}/** Removes a value from the set. Returns true if the set contained the specified element. */bool remove(int val) {//查找是是否在map中存在&＃xff0c;如果不存在则返回falseif(data_map.count(val) &＃61;&＃61; 0){return false;}else{//否则&＃xff0c;和数组尾部数据位置交换&＃xff0c;删除掉尾部数据int tail &＃61; data[data.size()-1];int pos1 &＃61; data_map[val]; //获取需要删除数据的位置int pos2 &＃61; data.size()-1; //最后一个元素的位置data_map[tail] &＃61; pos1;data_map[val] &＃61; pos2;data[pos1] &＃61; tail; //将需要删除的元素和尾部元素交换data_map.erase(val); //删除哈希表中的数据data.pop_back(); //删除数组中的datareturn true;}}/** Get a random element from the set. */int getRandom() {int t &＃61; data.size();int random_num &＃61; rand()%t;return data[random_num];}
};