假设我有一个包含以下字段的对象列表(或散列图等，只要它最快):名称、添加时间和删除时间。给我的列表已经按删除时间排序。现在，给定时间 T，我想过滤(从列表中删除)列表中的所有对象，其中: 时间 T 大于对象的移除时间或 T 小于对象的添加时间。 因此经过处理后，列表应该只包含 T 落在由添加时间和删除时间指定的范围内的对象。
我知道我可以通过遍历每个单独的对象在 O(n) 时间内轻松完成此操作，但我想知道是否有更有效的方法考虑列表已经按第一个谓词排序(时间删除)。
*另外，我知道我可以很容易地删除所有删除时间小于 T 的对象，因为列表是预排序的(可能在 O(log n) 时间内，因为我进行了二进制搜索以找到小于和的第一个元素然后删除列表的第一部分直到该对象)。
(不相关的附加信息:我将使用 C++ 编写任何代码)
最佳答案
不幸的是，您的最快选择是 O(n)。 除非它们是关于可以被利用的添加时间和删除时间之间的差异(例如最大时间跨度)的隐藏要求。
如您所说，您可以在删除的时间等于(或第一个大于)删除的时间处开始搜索。不幸的是，您需要浏览列表的其余部分，看看添加的时间是否少于您的时间。
因为比较排序最多是 O(n*log(n))，所以您不能再次对对象进行排序以提高性能。
有一件事，根据应用程序的启发式方法，按添加日期的顺序接收数据可能是有益的，但这在您和您获取数据的任何地方之间。
关于algorithm - 使用第二个谓词有效地过滤掉已排序的数据，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24038657/