我有一个元素列表,其中每个元素都是非负整数范围。我想以
例子:
假设我拥有的列表为
是否可能实现这一点?如果不行,用复杂度高于
O(n)
方式使用单个循环过滤列表,以使仅分离最大的未包含范围。此列表将始终按照每个范围的起始整数排序。封闭的范围元素可能会在封闭范围元素之前或之后出现在列表中。例子:
假设我拥有的列表为
{[0-12],[5-15],[5-20],[10-20],[11-30],[25-42],[28-40]}
。 在此列表中,范围[5-15]
和[10-20]
落在范围[5-20]
内,因此我需要舍弃它们。同样,范围元素[28-40]
也被舍弃,因为它落在范围[25-42]
内。 我希望使用单个循环进行此过滤,以实现O(n)
时间复杂度。是否可能实现这一点?如果不行,用复杂度高于
O(n)
的方式进行过滤的最佳方法是什么?Java中的解决方案将非常好。
start, end
排序的 - 这样永远都是这样吗?对于部分重叠的范围,比如1-6, 3-8
,你想要做什么? - AakashM