如何找到落在给定区间内的数组元素？

Question

这是一个面试问题。

给定一个整数数组和一个区间的流（一对整数），找出在每个流区间内的数组元素。你会使用什么样的数组预处理方法？

- Michael

---

我个人会选择桶排序。创建n个桶，其中n是区间的数量。然后在O（n）时间内获得结果。 - Jehanzeb.Malik

Answer 1

一种选项是对数组进行预处理，将其按升序排序。完成后，您可以通过在排序后的数组上执行两个二分搜索来查找落在区间内的所有元素 - 一个用于查找第一个大于或等于区间起点的元素，另一个用于查找不大于区间终点的最后一个元素 - 然后遍历数组以输出该范围内的所有元素。

如果使用标准排序算法（如快速排序或堆排序），则此过程需要O(n log n) 的时间进行预处理，但如果使用基数排序，则可以在O(n log U) 的时间内完成（这里，U是范围内的最大整数）。然后查询每个需要O(log n + k) 的时间，其中n是元素数量，k是范围内的元素数量。

如果你想变得更加高级，你可以使用van Emde Boas tree，一种专门用于存储整数的数据结构，以指数级别加快速度。如果您正在使用的最大整数值为U，则可以在O(n log log U)的时间内构建该结构，然后在O(log log U)的时间内执行端点范围搜索。然后，您可以在每个元素中以O(log log U)的时间找到所有范围内的元素，从而提供了一个O(k log log U)算法，用于查找范围内的所有匹配项。

希望这有所帮助！

- templatetypedef

Answer 2

将数组排序，然后进行二分查找以找到第一个大于区间起点的元素的索引，再次查找第一个小于区间终点的元素，并返回两者之间的所有整数。每次查询的时间复杂度为O(log N)，其中N是整数的数量。

- Hari Menon

---

这难道不就是和我的答案一模一样吗？:-) - templatetypedef

是的，你比我先完成了，尽管我写得更少 :( - Hari Menon

这就是为什么更加详细的解释从来不会是一种罪过，@HariShankar :-) - Richard

Answer 3

答案取决于您的需求：

您有多少个间隔，比如M？

当然，如果M很大且间隔也很大，则使用M * O（N logN）是过度的。

另一种方法：使用O（N）额外空间。

prefix[i] = number of numbers in range 0 to i 

可以在O(N)的时间内完成。

现在，每个查询需要O(1)的时间：

query[l,r] = prefix[r] - prefix[l - 1] + 1

因此，总时间复杂度为 O(N logN + M)。

- Aseem Goyal

---

你的答案对于任何查询都会返回1！ - Pham Trung

Answer 4

根据数组元素进行索引怎么样？

for (i in original_array) indexed_array[original_array[i]] = original_array[i]

for (j in stream) {
  for (k=stream[j][0]; k<=stream[j][1]; k++) 
    if (indexed_array[k]) return indexed_array[k]
}

或者用索引代替整数：

for (i in original_array) indexed_array[original_array[i]] = i

- גלעד ברקן