使用O(n)时间复杂度过滤列表元素

Question

我有一个元素列表，其中每个元素都是非负整数范围。我想以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中的解决方案将非常好。

- swap310

---

你对列表呈现顺序有什么保证？在你的例子中，它是按 start, end 排序的 - 这样永远都是这样吗？对于部分重叠的范围，比如 1-6, 3-8，你想要做什么？ - AakashM

相关链接：https://dev59.com/SIDaa4cB1Zd3GeqP_RGJ - sp00m

使用区间树可以保证O(nlogn)的时间复杂度。 - Steve Benett

假设它们按开始值排序，您可以通过合并重叠的连续范围来执行 O(n)。当它们不再重叠时，您将转移到下一个范围。 - Peter Lawrey

合并后，这些范围实际上会形成一个单独的“0-42”大范围，对吗？这是您要寻找的内容吗？ - sp00m

Answer 1

如果两个元素的起始位置相同，但是后一个元素的结束位置大于等于前一个元素，则后一个元素会覆盖前一个元素。 同样，如果下一个元素的结束位置小于当前元素的结束位置，则当前元素也会覆盖下一个元素。

因此，您需要遍历列表并比较当前和下一个元素。

如果它们具有currentStart = nextStart，并且nextEnd>=currentEnd -> 则删除当前元素。

否则，如果nextEnd <= currentEnd -> 则删除下一个元素。

- StanislavL

---

可能会有所帮助，给出一个简短的正确性证明。 - Bernhard Barker

Answer 2

在伪代码中，合并周期可以这样做：

def merge(l:list[period], e:period):
    if l == nil:
        return list(e)
    else:
        lh = l.head
        ll = l.tail
        if e.end < lh.start: 
            return e::l // original list prepended with e
        else if lh.end < e.start:
            return lh::merge(e,ll) // head + trying to merge period with the tail
        else: //overlap, make new period from e and list head and merge it with tail
            newstart = min(e.start, lh.start)
            newend = max(e.end, lh.end)
            return merge(period(newstart,newend), ll)

在你的情况下，你需要进行输入/输出合并，但是思路是类似的。

- Ashalynd