arrays - 查找数组中给定范围内的元素数

Question

例如，假设我有一个包含整数的数组:

1 3 4 9 10

我想找到 1 到 9(含)之间的元素个数，因此它应该返回 4(因为有 4 个整数 [1,3,4,9] 介于 1 到 9(含)之间)。

我考虑这样做的一种方法是首先将每个整数 J 放在数组的 Jth 位置，这样可以在常量中查询整数是否存在时间。然后你可以简单地遍历范围并检查每个数字是否存在，但是对于大数字来说这会花费太长时间。

最快的方法是什么？

Answer 1

只需将元素放在排序数组中，然后在查询时使用 binary search (两次)找到较低和较高的数字，你得到两个索引 l (lower),u (upper)。答案是 u-l + 1
复杂度为O(logN) - 其中N 是数组中元素的数量。

索引复杂度(初始化数组，只完成一次)对于 sotring 是 O(nlogn)。

在你的例子中:

• 二分查找 1 得到 l=0
• 二分查找 9 得到 u=3
• 答案 = u-l+1 = 3-0+1 = 4

注意:如果数组包含重复项或数字可能不存在 - 需要一些额外的工作 - 但如何做的想法保持不变。