以O（n）时间复杂度过滤出列表元素

我有一个元素列表，其中每个元素都是非负整数范围。我想过滤列表，只有最大的未封闭范围被分离出来。我想用O(n)的方式做到这一点与单循环。该列表将始终按照每个范围的起始整数排序。封闭范围元素可以在列表中的封闭范围元素之前或之后出现。以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中的解决方案会很好。

来源

2014-05-30 Swapnil Nawale

对于在您的示例中列表将按照“开始，结束”排序的顺序，您有什么担保？会永远如此吗？你想用部分重叠的范围做什么，例如'1-6，3-8'？ – AakashM

列表中的元素仅按范围的开始排序。部分重叠不会被滤除。 –

相关：http://stackoverflow.com/q/23887686/1225328 – sp00m

如果元素具有相同的范围起点但大于或等于结束点，则元素可能吞下前一个元素。如果下一个范围的结束小于当前元素的结束，元素也可以吞下。

所以你通过列表并比较当前和下一个元素。

如果他们有currentStart = nextStart和nextEnd> = currentEnd - >删除当前。

else else nextEnd < = currentEnd - > next next。

来源

2014-05-30 09:38:40 StanislavL

给出一个正确性的简短证明可能会有所帮助。 – Dukeling

伪代码，合并期间可以做这样的：

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)

你的情况，你必须diff的I/O合并，但这个想法是相似的。

来源

2014-05-30 09:58:49 Ashalynd

以O（n）时间复杂度过滤出列表元素

回答

相关问题