题目描述

给定一个非负整数的数据流输入 a1,a2,…,an,…,将到目前为止看到的数字总结为不相交的区间列表。

例如,假设数据流中的整数为 1,3,7,2,6,…,每次的总结为:

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

进阶:
如果有很多合并,并且与数据流的大小相比,不相交区间的数量很小,该怎么办?

提示:
特别感谢 @yunhong 提供了本问题和其测试用例。

https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals/

解法1

这道题我们使用TreeMap来解决。TreeMap的底层实现是R-B Tree,它的平衡性很好,对于get、put、remove、contains等操作都能够达到O(logn)的时间复杂度。我们使用的TreeMap的Key为插入操作的值,Value为能够表示插入值的最小区间。例如,我们向map中插入2,用[2,2]能够表示,用[1,3]能够表示,用[-1000,1000]也能够表示,但是我们选择最小的区间[2, 2],这样做能做到题目要求的“目前为止看到的数字总结为不相交的区间列表“。

这里我们还用到了TreeMap提供的两个重要的操作floorEntry与ceilingEntry。floorEntry(k)返回小于等于k的最大元组;ceilingEntry(k)返回大于等于k的最小元组。我们记leftValInterval = map.floorEntry(val),rightValInterval = map.ceilingEntry(val)。

图1 插入值与区间的关系

我们将插入的值与区间已有的值的关系分为图1的6种情况。case1、case3、case5表示已有的区间能够表示插入的值,其实case5能够和case1或case3合并。case2与case4表示插入值与已有的区间连续,那么将已有的区间扩大一个单元就能够表示插入值,例如向[1, 3]插入4,向[3, 4]插入2。case6表示如果有了插入值,就能够使得已有的左右区间连续,例如向[1, 4]和[6, 9]插入5。

如果我们清晰的分析出来这些情况,编写代码就不难了。对于新插入的值val,我们首先判断他们在TreeMap中是否存在,如果存在则返回。否则,查询val的floorEntry与ceilingEntry。如果floorEntry的右边界等于val-1,就说明我们可以将val合并到floorEntry对应的区间,将区间扩大,如图1中case2所示。对于ceilingEntry的处理同理,如图1中case4所示。如果floorEntry的右边界等于val-1且ceilingEntry的左边界等于val+1,说明我们将val插入到这两个区间后,能够使得这两个区间连续,如图1中case6所示。如果不满足图1中任何一个case,说明val无法被TreeMap中已有的区间无法表示,我们需要向TreeMap插入新区间[val, val]。

全部代码如下所示,时间复杂度O(nlogn),空间复杂度O(n)。

import java.util.Map;
import java.util.TreeMap;

class SummaryRanges {
    private TreeMap<Integer, int[]> map; // key inserted val, value the interval included the val
    /**
     * Initialize your data structure here.
     */
    public SummaryRanges() {
        map = new TreeMap<>();
    }

    public void addNum(int val) {
        if (map.containsKey(val))
            return;

        Map.Entry<Integer, int[]> leftValInterval = map.floorEntry(val);
        Map.Entry<Integer, int[]> rightValInterval = map.ceilingEntry(val);


        int[] leftInterval = leftValInterval != null ? leftValInterval.getValue() : null;
        int[] rightInterval = rightValInterval != null ? rightValInterval.getValue() : null;


        // Left or Right interval can expresses val
        if (leftInterval != null && leftInterval[0] <= val && leftInterval[1] >= val ||
                rightInterval != null && rightInterval[0] <= val && rightInterval[1] >= val)
            return;

        // merge left & right
        if (leftInterval != null && rightInterval != null && leftInterval[1] == val - 1 && rightInterval[0] == val + 1) {
            // keep left, remove right
            leftInterval[1] = rightInterval[1];
            map.remove(rightValInterval.getKey());
        } else if (leftInterval != null && leftInterval[1] == val - 1)
            leftInterval[1] = val;
        else if (rightInterval != null && rightInterval[0] == val + 1)
            rightInterval[0] = val;
        else
            map.put(val, new int[]{val, val});
    }

    public int[][] getIntervals() {
        return map.values().toArray(new int[map.size()][]);
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *