5

这是一道面试题。

给定一个整数数组和一个区间流（整数对），找出该数组中落入流的每个区间的元素。你会使用什么数组预处理？

4

4 回答 4

9

一种选择是通过将数组按升序排序来预处理数组。完成此操作后，您可以通过对已排序的数组进行两次二进制搜索来找到位于某个区间内的所有元素 - 一次查找大于或等于区间开始的第一个元素，另一次查找最后一个元素不大于间隔的端点 - 然后遍历数组以输出该范围内的所有元素。

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

如果您想变得花哨，可以使用van Emde Boas 树（一种用于存储整数的专用数据结构）以指数方式加快速度。如果您正在使用的最大整数值是 U，那么您可以在 O(n log log U) 时间内构建结构，然后在 O(log log U) 时间内进行端点范围搜索。然后，您可以在 O(log log U) 的时间内找到范围内的所有元素，给出一个 O(k log log U) 算法来查找范围内的所有匹配项。

希望这可以帮助！

于 2013-02-16T18:24:33.110 回答
3

答案取决于您的要求：

你有多少间隔说M？

当然，使用 M * O(N logN) 是矫枉过正的，尤其是当 M 很大并且间隔也很大时。

另一种方法： 使用 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)

于 2014-02-11T13:55:47.600 回答
3

对数组进行排序，然后进行二分查找，查找数组中大于区间 start 的第一个元素的索引，然后再次查找小于区间 end 的第一个元素，并返回其间的所有整数. 对于O(log N)每个查找，其中 N 是整数的数量。

于 2013-02-16T18:25:40.320 回答
1

如何根据元素索引数组呢？

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
于 2013-02-16T20:11:38.540 回答