一种数据结构，用于确定在特定范围内有多少元素

本文关键字：范围内 元素 多少 用于 一种 数据结构 | 更新日期: 2023-09-27 18:06:39

假设我有一组数字。我需要计算给定范围内有多少个数。例如:对于给定的集合:{3, 4, 7, 10, 15, 30}:

numbers in range (0, 6) = 2
numbers in range (8, 40) = 3
numbers in range (0, 50) = 6

哪种结构最适合这个目的?我所说的最佳是指具有最快执行所述操作的结构。此外，快速插入和删除也将赞赏…

一种数据结构，用于确定在特定范围内有多少元素

如果给定的数字集从未改变，一个简单的选择是将数字按升序排序，然后在范围的端点上使用二进制搜索来确定排序序列中包含在范围内的第一个元素的位置以及第一个不在范围内的元素的位置。然后，您可以减去这两个位置的差来计算范围内有多少元素，或者只是遍历该范围以确定该范围内的所有数字。使用快速排序算法，如快速排序或堆排序，排序可以在O(n log n)时间内完成，每个查询只需要O(log n)时间来执行两个不同的二进制搜索。

你可以通过多种方式加速这个过程。例如，如果您知道数字或多或少是均匀分布的，则可以使用插值搜索而不是二进制搜索来进行查找。每次查询的预期时间为O(log log n)，这比以前快了很多。如果你知道所有的数字都在[0,N]的范围内，你可以使用更高级的数据结构，比如van Emde Boas树，在最坏的情况下，将所有的操作加速到O(log log N)。

另一方面，如果数字集可以增长和缩小，那么您可能需要考虑使用平衡二叉搜索树来存储您的数字。然后，您可以在树上进行有效的搜索(时间为O(log n))，以确定范围内的第一个数字和第一个不在范围内的数字。

希望这对你有帮助!

这是计算几何中一个研究得很好的问题，它被称为范围搜索。虽然你有1-D版本。问题是每个操作有多常见，如果插入和删除很少，在这种情况下，您可以将它们制成表格。这将给你O(n^2)的存储空间和常数查询时间。

templatetypedef的答案是好的，如果您的数据集不会随着时间的推移而改变，但是您提到需要快速插入和删除。

[编辑:David Eisenstat已经解释了如何在平衡二叉树中进行两次O(log n)搜索，增加每个节点的计数，从而有效地计数给定范围内的元素。]

在任何情况下，如果需要快速更新，理想的数据结构是Fenwick树或BIT树。该数据结构为以下操作提供O(log n)保证:

  • 查询:统计0到任意给定数之间的元素个数
  • 更新:从multiset中插入或删除任意给定数量的拷贝。

两个查询调用允许您使用count(j) - count(i)计算任何给定范围[i, j)中的元素数量。

对Fenwick树的查询和更新都只涉及简单的位操作和对单个数组的查找，因此使用这种数据结构将在O(log n)上产生非常有竞争力的常数——我预计它将比在更新下维护平衡二叉树快得多，后者需要指针操作和树重新平衡。

这有什么不对?

    static int Count(IList<int> set, int min, int max)
    { 
        int count = 0;
        foreach (int i in set)
            if (i < max && i > min)
                count++;
        return count;
    }
相关文章：