leetcode| 56. 合并区间

ustca 2020-02-11 原文

给出一个区间的集合，请合并所有重叠的区间。

示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路

将区间按照左端点升序排列，同《算法导论》——活动选择问题。
时间复杂度O(nlgn)，空间复杂度O(n)。

代码

class Solution {
    public int[][] merge(int[][] intervals) {
        int length = intervals.length;
        if(length < 2) return intervals;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if(a[0] == b[0]) {
                    return b[1] - a[1];
                } else {
                    return a[0] - b[0];
                }
            }
        });
        List<int[]> ans = new LinkedList<int[]>();
        int x = intervals[0][0];
        int y = intervals[0][1];
        for(int i = 1; i < length; i++) {
            if(intervals[i][0] > y) {
                ans.add(new int[]{x, y});
                x = intervals[i][0];
                y = intervals[i][1];
            } else if(intervals[i][1] > y) {
                y = intervals[i][1];
            }
        }
        ans.add(new int[]{x, y});
        int n = 0;
        int[][] res = new int[ans.size()][2];
        for(int[] i : ans) {
            res[n][0] = i[0];
            res[n++][1] = i[1];
        }
        return res;
    }
}

笔记

ArrayList和LinkedList的大致区别：
1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3.对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。
ans.add(new int[]{x, y})
add方法只会将引用地址放入集合中,每次add需要new一个对象。
add函数源码：

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

结点的添加仅操作了地址。

链接：https://leetcode-cn.com/problems/merge-intervals