主页 / 问题 / 746694
Accepted
Qwertiy
Asked:2020-11-19 20:16:27 +0000 UTC2020-11-19 20:16:27 +0000 UTC

有效地找到集合中的中间元素

  • 772

std::set通常用二叉搜索树表示。它有方法begin和end，可以让你得到最小值和最大值，以及二进制搜索lower_bound。upper_bound但是如果我需要一个迭代器指向集合中间的元素（或者其中一个，如果它有偶数个元素）怎么办？

有没有一种有效的方法来做到这一点（O(log(size))代替O(size)）？

{1} => 1
{1,2} => 1 или 2
{1,2,3} => 2
{1,2,3,4} => 2 или 3 (но в ту же сторону от середины, что и с {1,2})
{1,312,10000,14000,152333} => 10000

PS：这个问题是英文的。

c++

3 个回答

  1. Best Answer

    或者，如果您确实使用set，则可以维护一个指向中间元素的迭代器以及该k迭代器之前的元素数。

    • 初始set为空，迭代set.end()器k为零
    • 向 中添加元素时set：
      • 新元素大于中位数 => 如有必要（如果k * 2 + 3 <= set.size()）我们将迭代器向前移动 1 并增加k1。
      • 新元素小于中位数 => 如有必要，将迭代器向后移动 1 并减少k1。
    • 当从 中删除一个元素时set，我们的行为类似，如有必要，将迭代器向前/向后移动 1
    • 因此，在任何给定时间，每个中值元素都有一个迭代器，维护该迭代器的额外成本是O(log n)每个插入/删除

    这里有一个关于英语 Stack Overflow 上关于同一件事的有用问题（没有删除，但想法是一样的）

    • 8

  2. 如果不想自己写笛卡尔树，那么可以使用gcc内置的数据结构rope

    • 2

  3. 我想不是。好吧，看，要在 BST 中找到最小值，你必须总是去左边的分支，最大值 - 到右边。现在你想找到平均值。而且从一开始就不知道该做什么。按照惯例，您在树的根部有“10”，您对内容一无所知。你要去哪？

    • 0

相关问题