获取随机元素并将其删除

Question

问题：我需要获取容器的随机元素并将其从该容器中删除。容器不需要排序。 我不关心顺序。

• Vector 可以在 O(1) 中获取随机元素，但只能在 O(N) 中删除
• 它O(1) 中的元素，但只能在 O(N) 中获取随机元素

所以我想出了一个想法，制作一个自定义向量，允许您删除任何元素通过其复杂度为 O(1)+ 的索引。 这个想法是交换最后一个元素和要删除的元素，然后使用 pop_back()。 如果您需要删除最后一个元素 - 只需pop_back()。 向量的顺序不会相同，但您可以获得快速删除方法。

据我了解，与我的解决方案相比，双端队列的索引访问速度更慢，删除复杂度更差，但我不能 100% 确定。

我很好奇是否存在按索引或按值按 O(1) 或 O(logN) 进行随机访问和元素删除的数据结构？

Answer 1

您已经找到了解决方案，而且看起来非常好。用 C++ 编写它的惯用方法不是创建另一个类（请不继承 std::vector），而只是编写一个函数：

template <typename T>
void remove_at(std::vector<T>& v, typename std::vector<T>::size_type n)
{
    std::swap(v[n], v.back());
    v.pop_back();
}

用法：

remove_at(v, 42);

这提供了与std::swap。

现在，如果您想返回该对象，并且您可以访问 C++11 编译器，则可以按以下方式执行。困难的部分是在所有情况下提供基本的异常保证：

template <typename T>
T remove_at(std::vector<T>&v, typename std::vector<T>::size_type n)
{
    T ans = std::move_if_noexcept(v[n]);
    v[n] = std::move_if_noexcept(v.back());
    v.pop_back();
    return ans;
}

实际上，如果在移动操作期间引发异常，您不希望向量处于无效状态。

Answer 2

复杂度为 O(n)

vec.erase(vec.begin() + randomIdx);
randomIdx 将介于 0 和 vec.size()-1 之间，

如果您想要 O(1) 复杂度，您可以使用列表容器，或者将元素与最后一个元素交换并删除它。 （正如其他人提到的）

Answer 3

是的，有一个解决方案，一个平衡良好的二叉树。

每个节点都需要存储每一侧的节点数。由此找到第 n 个元素的时间复杂度为 O(log N)。

删除第 n 个元素也是 O(log N)，因为您必须遍历回树以更正所有计数。任何重新平衡最多也将是 O(log N)。

如果没有叶节点比另一个叶节点深 2 个节点，则认为树是平衡的。查找 AVL 树以获得重新平衡算法。

如果标准库“开放”用于 std::set 和 std::map 的树作为在自定义树中使用的公共接口，那实际上会很好。