目录

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

合并区间问题

以数组 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: