3

所以我试图解决这个问题： http: //oj.leetcode.com/problems/merge-intervals/

我的解决方案是：

public class Solution {

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
    // Start typing your Java solution below
    // DO NOT write main() function
    // ArrayList<Interval> result = new ArrayList<Interval>();

    //First sort the intervals
    Collections.sort(intervals,new Comparator<Interval>(){
        public int compare(Interval interval1, Interval interval2) {
            if(interval1.start >  interval2.start) return 1;
            if(interval1.start == interval2.start) return 0;
            if(interval1.start <  interval2.start) return -1;
            return 42;
        }
    });

    for(int i = 0; i < intervals.size() - 1; i++){
        Interval currentInterval = intervals.get(i);
        Interval nextInterval = intervals.get(i+1);
        if(currentInterval.end >= nextInterval.start){
            intervals.set(i,new Interval(currentInterval.start,nextInterval.end));
            intervals.remove(i+1);
            i--;
        }
    }

    return intervals;   
}
}

我看到一些博客使用完全相同的解决方案，但被接受了，但我的被拒绝了，因为它需要太长时间。你能告诉我为什么它需要比预期更长的时间吗？干杯

编辑：已解决，删除成本太高，使用新的数组列表存储结果更快

4

2 回答 2

2

最初，您正在对所有间隔进行排序 - 由于 javadocs，此操作具有复杂性 O(N*log(N))

但是，在那之后，正如我所注意到的 - 你正在迭代 ArrayList，有时会从中删除元素。

但是从 ArrayList 中删除一些元素的复杂度为 O(N)（因为 ArrayList 的底层实现是普通数组 - 从数组中间删除任何元素，需要移动该数组的整个右侧部分）。

当您在循环中执行此操作时 - 最后，您的算法的复杂性将是 O(N^2)。

在这种情况下，我建议您使用 LinkedList 而不是 ArrayList。

于 2013-09-18T14:33:24.180 回答
1

您可以通过使用一次计算而不是 3 次比较来改进排序：

Collections.sort(intervals,new Comparator<Interval>(){
    public int compare(Interval interval1, Interval interval2) {
        return interval1.start - interval2.start;
    }
});
于 2013-09-18T14:28:10.307 回答