LeetCode-56. 合并区间-Java-medium

题目链接

法一（排序）

    /**
     * 时间复杂度：O(nlogn)
     *
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]); // 对第一维元素进行升序排列
        List<int[]> merge = new ArrayList<>();
        for (int[] interval : intervals) {
            int pre = merge.size() - 1;
            if (merge.size() == 0 || merge.get(pre)[1] < interval[0]) { // 上一区间的第二维 < 当前区间的第一维
                merge.add(interval); // 如果列表为空，或者当前区间与上一区间不重合，直接添加
            } else { // 上一区间的第二维 >= 当前区间的第一维
                merge.get(pre)[1] = Math.max(merge.get(pre)[1], interval[1]); // 否则，与上一区间进行合并
            }
        }
        return merge.toArray(new int[0][]);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

法二（位图）

    /**
     * 法二（位图）
     * 1.  对于[5,5]这种情况
     *     start和end不可以相等，否则set时没有效果，nextSetBit和nextClearBit时也会出现错误
     *     若start = interval[0]，end = interval[1]，则start == end，错误
     * 2.  对于[1,4] [5,6]这种情况
     *     （1）若start = interval[0]，end = interval[1] + 1
     *         [1,4] [5,6] -> [1,5) [5,7) -> [1,6] 错误
     *     （2）若start = interval[0] * 2，end = interval[1] * 2 + 1
     *         [1,4] [5,6] -> [2,9) [10,13) -> [1,4] [5,6] 正确
     *
     * @param intervals
     * @return
     */
    public int[][] merge_2(int[][] intervals) {
        BitSet bit = new BitSet();
        int max = 0;
        for (int[] interval : intervals) {
            int start = interval[0] * 2;
            int end = interval[1] * 2 + 1;
            bit.set(start, end, true);
            max = Math.max(max, end);
        }
        int index = 0, cnt = 0;
        while (index < max) {
            int start = bit.nextSetBit(index);
            int end = bit.nextClearBit(start);
            intervals[cnt++] = new int[]{start / 2, (end - 1) / 2};
            index = end;
        }
        int[][] ans = new int[cnt][2];
        System.arraycopy(intervals, 0, ans, 0, cnt);
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

本地测试

        /**
         * 56. 合并区间
         */
        lay.showTitle(56);
        Solution56 sol56 = new Solution56();
        int[][] intervals56 = new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        arrayOpt.showIntTwoDimArray(intervals56, intervals56.length);
        int[][] ans56_1 = sol56.merge(intervals56);
        int[][] ans56_2 = sol56.merge_2(intervals56);
        arrayOpt.showIntTwoDimArray(ans56_1, ans56_1.length);
        arrayOpt.showIntTwoDimArray(ans56_2, ans56_2.length);
1
2
3
4
5
6
7
8
9
10
11