3

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

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

什么样的结构最适合这个目的？最好的意思是具有最快执行所述操作的结构。快速插入和移除也将不胜感激......

4

4 回答 4

7

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

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

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

希望这可以帮助！

于 2013-03-31T22:05:53.420 回答
3

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

于 2013-03-31T22:23:08.073 回答
2

如果您的数据集不会随时间而变化，则 templatetypedef 的答案很好，但您提到需要快速插入和删除。 [编辑：David Eisenstat 解释了平衡二叉树的两次 O(log n) 搜索如何通过每个节点计数来有效地计算给定范围内的元素。]

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

  • 查询：计算 0 到任意给定数字之间的元素个数。
  • 更新：将某个给定数量的任何给定数量的副本插入或从多集中删除。

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

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

于 2013-04-01T09:49:22.973 回答
1

这有什么问题？

    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;
    }
于 2013-03-31T22:10:06.683 回答