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(hash.count(val)) return false;
hash[val] = vec.size();
vec.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(hash.count(val)==) return false;
int pos = hash[val];
hash[vec.back()] = pos;
swap(vec[pos], vec[vec.size()-]);
hash.erase(val);
vec.pop_back();
return true;
}
/** Get a random element from the set. */
int getRandom() {
return vec[rand()%vec.size()];
}
private:
unordered_map<int, int> hash;
vector<int> vec;
};
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* bool param_1 = obj.insert(val);
* bool param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/数据结构设计问题，从网上找的参考答案。
根据以上的思路，写了一份python版本的代码：
class RandomizedSet:
def __init__(self):
"""
Initialize your data structure here.
"""
self.dic = dict()
self.l = list()
self.length = def insert(self, val: int) -> bool:
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
"""
if val in self.dic:
return False
else:
self.dic[val] = self.length
self.l.append(val)
self.length +=
return True def remove(self, val: int) -> bool:
"""
Removes a value from the set. Returns true if the set contained the specified element.
"""
if val not in self.dic:
return False
else:
self.dic.pop(val)
self.l.remove(val)
self.length -=
return True def getRandom(self) -> int:
"""
Get a random element from the set.
"""
rnd = int(random.uniform(, self.length))
key = self.l[rnd]
return key