假设我有一组数字。我需要计算给定范围内有多少数字。
例如:对于给定的集合:{3, 4, 7, 10, 15, 30}:
numbers in range (0, 6) = 2
numbers in range (8, 40) = 3
numbers in range (0, 50) = 6
哪种结构最适合该目的？我所说的最好的意思是执行该操作最快的结构。快速插入和移除也将不胜感激......
最佳答案
如果给定的一组数字永远不变，一个简单的选择是将数字按升序排序，然后使用 binary search在范围的端点上确定排序序列中包含在范围内的第一个元素所在的位置以及不在范围内的第一个元素所在的位置。然后，您可以减去这两个位置的差来计算该范围内有多少元素，或者只是遍历该范围以确定该范围内的所有数字。使用像快速排序或堆排序这样的快速排序算法，排序可以在 O(n log n) 时间内完成，并且每个查询只需要时间 O(log n) 来进行两次不同的二进制搜索。
您可以通过多种方式加快此过程。例如，如果您知道数字分布大致均匀，则可以使用 interpolation search而不是二进制搜索来进行查找。这需要预期的时间 O(log log n) 来执行每个查询，这比以前快了指数级。如果你知道数字都在 [0, N) 范围内，你可以使用更高级的数据结构，如 van Emde Boas tree在最坏的情况下将所有操作加速到 O(log log N)。
另一方面，如果数字集可以增长和缩小，那么您可能需要考虑使用平衡二叉搜索树来存储您的数字。然后，您可以在树上进行高效搜索(时间为 O(log n))以确定范围内的第一个数字和不在范围内的第一个数字。
希望这对您有所帮助!
关于c# - 用于确定特定范围内有多少元素的数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15735049/