假设区间列表可能是 [[1,3],[2,4],[6,12]] 并且查询时间 T = 3。上述列表中为 3 的区间数为 2（即） [[1,3]，[2,4]]。是否可以在 O(logn) 时间内做到这一点？
问问题
367 次
3 回答
2
在一般情况下，这不能在 O(log n) 时间内完成。
您可以在开始时间进行二分搜索以找到可能包含查询时间的最后一个间隔，但由于结束时间没有隐含的排序，您可以从列表的开始顺序搜索到您确定为最后的项目确定查询时间是否在任何这些时间间隔内。
例如，考虑[(1,7),(2,11),(3,8),(4,5),(6,10),(7,9)]查询时间为 7 的 。
开始时间的二进制搜索会告诉您所有的时间间隔都可能包含查询时间。但是因为结束时间没有任何特定的顺序，所以你不能对它们进行二进制搜索。您必须查看每个单独的时间间隔以确定结束时间是否大于或等于查询时间。在这里，您看到(4,5)不包含查询时间。
于 2018-12-31T20:42:28.647 回答
0
嗯，需要注意的一点是，对于包含 T 的区间，它的开始时间必须小于或等于 T。由于这些是按开始时间排序的，因此您可以使用基本的二分查找来消除所有也开始的时间在 O(log n) 时间的后期。
如果我们可以假设这些也按结束时间排序——也就是说，没有一个区间完全包含前一个区间——那么你可以使用另一个二分搜索来消除所有结束时间在 T 之前的那些。这将保持运行O(log n) 中的时间。
如果我们不能做出这样的假设，事情会变得更加复杂，我想不出任何比 O(n log n) 做得更好的方法 [通过按结束时间对剩余列表进行排序并对其执行另一次二进制搜索] . 也许有办法？
编辑如下 Qbyte 所说，最后的排序是多余的；您可以通过对剩余集合进行简单的线性搜索将其降低到 O(n)。再说一次，如果你仍然使用 O(n) 解决方案，你也可以跳过整个算法，只对原始集合进行线性搜索。
于 2018-12-31T18:22:38.833 回答
0
让我们假设间隔按开始时间排序。二进制搜索O(log n)将消除不能包含T的区间。剩下的可能。
假设结束时间也没有排序（OP）
您必须扫描剩余的O(n)，对它们进行计数。总复杂度O(n)。鉴于此，您可能从未进行过二进制搜索而只是扫描了整个列表。
假设结束时间也已排序
如果其余的也按结束时间排序，则可以进行另一次二进制搜索，将复杂度保持在O(log n)。
但你还没有完成。你需要计数。
你知道从计数开始。如果你不这样做，你就不能进行二进制搜索。您将知道每个二进制搜索的最后测试的索引。从这里开始，它是一个O(1)计算选项。
因此，此选项的总复杂度为O(log n)。
于 2018-12-31T19:26:14.550 回答