合并区间 LeetCode 56/57 BitSet 的妙用

zsqw123 收录于手记

2021-04-21 约 969 字预计阅读 2 分钟次阅读

合并区间问题

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

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

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

1 <= intervals.length <= 10000
intervals[i].length == 2
0 <= starti <= endi <= 10000

思路

看到这道题的数据这么小, 我就直接想到用bit位来记录每个位置是否被覆盖, 然后遍历导出, 我也确实这么做了, 但是我自己实现后实现相当复杂, 我就当时在想为什么这种需求按道理来说应该有现成的实现啊, 于是我找到了BitSet, 不同于int占用四个字节, boolean占用一个字节, BitSet粒度更细, 实现了在每个bit位上来记录信息, 较为高效, 列举一些常用方法:

Modifier and Type	Method and Description
`void`	`and/or/xor(BitSet set)` 与另一个`BitSet`逻辑运算所有位
`int`	`cardinality()` 返回值为`true`的数量
`void`	`clear()` 将所有位设置为 `false`
`void`	`clear/flip/get(int bitIndex)` 将指定位 `false`/补码/获取
`void`	`clear/flip/get(int fromIndex, int toIndex)` 区间: `[fromIndex,toIndex)`
`boolean`	`isEmpty()` 是否包含 `true`
`int`	`length()` 最高位的索引 + 1
`int`	`nextClearBit(int fromIndex)` 返回指定索引后第一个`false`位的索引
`int`	`nextSetBit(int fromIndex)` 返回指定索引后第一个`true`位的索引
`int`	`previousClearBit(int fromIndex)`/`previousSetBit(int fromIndex)`
`void`	`set(int bitIndex)` 将指定索引处的位设置为 `true` `set(int bitIndex, boolean value)` `set(int fromIndex, int toIndex)` 区间:`[fromIndex,toIndex)` `set(int fromIndex, int toIndex, boolean value)`
`int`	`size()` 返回实际使用的空间位数

那这样就相当简单了, 遍历加入所有情况, 然后遍历输出

但是注意! [0,1]和[2,3]这两个区间虽然紧挨着, 但是不可以合并, 我们需要× 2来保证紧挨着的区间不会合并, 我这边直接使用了位移运算, 不过复杂度其实可达O(N^2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


public int[][] merge(int[][] intervals) {
    ArrayList<int[]> res=new ArrayList<>();
    BitSet bits=new BitSet();
    for(int[] ints:intervals)bits.set(ints[0]<<1,(ints[1]<<1)+1);
    int end=0;
    for(;;){
        int n=bits.nextSetBit(end);
        if(n==-1) break;
        end=bits.nextClearBit(n);
        res.add(new int[]{n>>1,(end-1)>>1});
    }
    return res.toArray(int[][]::new); // Java 11+ only
}

同上, 57题其实可以照抄过的, 但是多了个有序条件我们可以利用一下, 复杂度 O(N)

 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


public int[][] insert1(int[][] intervals, int[] newInterval) {
    ArrayList<int[]> res=new ArrayList<>(intervals.length);
    BitSet bits=new BitSet();
    int last0,last1;
    final int len=intervals.length;
    if(len>=1){
        last0=intervals[0][0];
        last1=intervals[0][1];
        for(int i=1;i<len;i++){
            int now0=intervals[i][0];
            int now1=intervals[i][1];
            if(now0>last0){
                bits.set(last0<<1,(last1<<1)+1);
                last0=now0;
                last1=now1;
            }else if(now0==last0) last1=Math.max(last1,now1);
        }
        bits.set(last0<<1,(last1<<1)+1);
    }
    bits.set(newInterval[0]<<1,(newInterval[1]<<1)+1);
    int end=0;
    for(;;){
        int n=bits.nextSetBit(end);
        if(n==-1) break;
        end=bits.nextClearBit(n);
        res.add(new int[]{n>>1,(end-1)>>1});
    }
    return res.toArray(int[][]::new);
}

links:

目录

合并区间 LeetCode 56/57 BitSet 的妙用

合并区间问题

思路