← 返回 meta 的题目列表Implement an O(1) Random-Pop Container
类型：online_judge
Implement a container of unique elements that supports:
insert(element): insert an element; do nothing if it already exists.
popRandom(): remove and return one currently stored element, with every stored element having equal probability.
Requirements:
Apart from random-number generation, both operations must run in expected O(1) time.
popRandom() returns None when the container is empty.
After removing a random item, the remaining elements must still be available for later random removal.
Input Format
The first line is the number of operations q. Each following line is one operation:
insert x
popRandom
Output Format
Print the return value for each popRandom. For reproducible tests, use random seed 0.
Example
Input
5
insert 10
insert 20
insert 30
popRandom
popRandom
Output
20
30
Constraints
1 <= q <= 2 * 10^5.
Example
Input
5
insert 10
insert 20
insert 30
popRandom
popRandom
Output
20
30