过滤出具有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中的解决方案会很棒.

Answer 1

如果元素具有相同的范围开始但更大或相等的结束,则元素可以吞下前一个元素.如果下一个范围的结束小于当前eleemnt的结束,那么该元素也可以吞下.

因此,您将浏览列表并比较当前和下一个元素.

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

else如果nextEnd <= currentEnd - >删除下一个.