pop哪一个元素,决定了queue, stack, priority_queue的不同。新加一个random_queue,等概率的从集合里取出一个元素pop
1)先用rand(int l, int r)得到一个随机位置,
2)和top交换
3)top--
思路:连续存储一般只有在边界add/remove才是O(1)的,否则会涉及shift。这里有个前提,就是要保持其余元素的相对顺序。如果不许要保持,就可以和边界交换
总结一下:假设数组中的一段是一个集合,这些操作:平移一个位置,删除任意位置的元素都是O(1)的
class random_queue {
vector<int> a;
void push(int e) {
a.push_back(e);
}
int pop() {
int i = rand() % a.size();
swap(a[i], a.back());
int ret = a.back();
a.pop_back();
return ret;
}
}