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

Question

例如,假设我有一个带整数的数组:

1 3 4 9 10

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

我想到这样做的一种方法是首先将每个整数J放在数组的第J个位置,以便查询整数是否存在可以在恒定时间内完成.然后你可以简单地浏览范围并检查每个数字是否存在,但这对于大数字来说需要太长时间.

最快的方法是什么？

Answer 1

只需将元素放在一个有序数组中,然后在查询中使用二进制搜索(两次)来查找低位数和高位数,就得到两个索引l (lower),u (upper).答案是那么u-l + 1
的复杂性是O(logN)-哪里N是你的数组中元素的个数.

索引复杂性(初始化数组,仅执行一次)O(nlogn)用于索引.

在你的例子中:

• 二元搜索1得到l = 0
• 二元搜索9收率u = 3
• answer = u-l + 1 = 3-0 + 1 = 4

注意:如果数组包含dupes或数字可能不存在 - 需要一些额外的工作 - 但是如何做到这一点的想法保持不变.