相关疑难解决方法(0)

这不是一个面试问题本身,因为我在我的项目中遇到过这个问题,但我认为这可能是一个不错的干预问题.

你有N对间隔,比如说整数.您需要在O(N)时间内识别出彼此重叠的所有间隔.例如,如果你有

{1,3} {12,14} {2,4} {13,15} {5,10}

答案是{1,3},{12,14},{2,4},{13,15}.请注意,您不需要对它们进行分组,因此结果可以按照示例中的任何顺序进行.

我刚刚投入O(N)时间因为KMP算法需要O(N)进行字符串搜索.:d

我想出的最好的,我现在在项目中使用的是O(N ^ 2).是的,蛮力非常难过,但没有人抱怨所以我不会重构它.:P仍然,我很好奇,如果一个更大的头脑有一个更优雅的解决方案.

所以我知道时间的复杂性:

for(i;i<x;i++){
   for(y;y<x;y++){
      //code
   }
}

是n ^ 2

但会:

for(i;i<x;i++){
   //code
}
for(y;y<x;y++){
   //code
}

是n + n？