如何查找落在给定间隔内的数组元素？

给定一个整数数组和一个数据流的间隔（整数对）可以找到数组中每个间隔的数组元素。你会用什么阵列预处理？

2013-02-16 Michael

我会亲自去的东西，如桶排序。制作n个桶，其中n是间隔数。然后在O（n）你会得到你的结果。 – 2013-02-16 18:24:52

一种选择是将数组按升序排序来预处理数组。一旦完成了这些操作，就可以通过在已排序的数组上进行两次二元搜索来查找属于某个时间间隔的所有元素 - 一个用于查找第一个大于或等于间隔开始的元素，另一个用于查找最后一个元素不大于间隔的终点 - 然后迭代整个数组以输出该范围内的所有元素。

这需要O（n log n）时间来进行预处理，如果您使用标准排序算法（如quicksort或heapsort），但可以在O（n log U）时间内完成，如果使用基数排序（这里U是范围中最大的整数）。查询然后每个都需要O（log n + k）时间，其中n是元素的数量，k是该范围内元素的数量。

如果你想变得很花哨，你可以通过使用van Emde Boas tree这个专门用于存储整数的数据结构以指数形式加速。如果你正在使用的最大整数值是U，那么你就可以建立时间为O结构（N日志记录U），然后执行端点范围搜索时间为O（log日志U）。然后您可以在时间O（log log U）中查找范围内的所有元素，从而给出一个O（k log log U）算法来查找范围内的所有匹配。

希望这会有所帮助！

来源

2013-02-16 18:24:33 templatetypedef

排序数组，然后做二进制搜索找到比发车间隔较大的数组中的第一个元素的索引，然后再次找到小于间隔结束的第一个元素，并返回所有中间的整数。对于每个查找，将是O(log N)，其中N是整数的数量。

来源

2013-02-16 18:25:40

这与我的回答不完全相同吗？ :-) – templatetypedef 2013-02-16 18:26:16

是的，你打我，尽管我写了更少:( – 2013-02-16 18:27:13

这就是为什么它永远不会是一种罪行_even more_解释，@HariShankar :-) – Richard 2014-10-03 05:04:38

关于索引根据其元素的数组是什么？

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-16 20:11:38

答案取决于你的需求：

你有多少时间间隔写成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-11 13:55:47

你的答案总是返回1的任何查询！ – 2014-02-13 09:42:16

@PhamTrung谢谢，有错误，更正。 – 2014-02-13 12:00:00

如何查找落在给定间隔内的数组元素？

回答

相关问题