将数据流变为多个不相交区间

352. 将数据流变为多个不相交区间

给你一个由非负整数 a₁, a₂, ..., a_n 组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。

实现 SummaryRanges 类：

SummaryRanges() 使用一个空数据流初始化对象。
void addNum(int val) 向数据流中加入整数 val 。
int[][] getIntervals() 以不相交区间 [start_i, end_i] 的列表形式返回对数据流中整数的总结。

示例：

输入：
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
输出：
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

解释：
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1);      // arr = [1]
summaryRanges.getIntervals(); // 返回 [[1, 1]]
summaryRanges.addNum(3);      // arr = [1, 3]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]]
summaryRanges.addNum(7);      // arr = [1, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]]
summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]

提示：

0 <= val <= 10⁴
最多调用 addNum 和 getIntervals 方法 3 * 10⁴ 次

进阶：如果存在大量合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办?

相似题目

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

class SummaryRanges { public: SummaryRanges() { } void addNum(int val) { } vector<vector<int>> getIntervals() { } }; /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges* obj = new SummaryRanges(); * obj->addNum(val); * vector<vector<int>> param_2 = obj->getIntervals(); */

golang 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2023-05-29 17:36:02

type SummaryRanges struct {
    *redblacktree.Tree
}

func Constructor() SummaryRanges {
    return SummaryRanges{redblacktree.NewWithIntComparator()}
}

func (ranges *SummaryRanges) AddNum(val int) {
    // 找到 l0 最大的且满足 l0 <= val 的区间 interval0 = [l0, r0]
    interval0, has0 := ranges.Floor(val)
    if has0 && val <= interval0.Value.(int) {
        // 情况一
        return
    }

    // 找到 l1 最小的且满足 l1 > val 的区间 interval1 = [l1, r1]
    // 在有序集合中，interval1 就是 interval0 的后一个区间
    interval1 := ranges.Iterator()
    if has0 {
        interval1 = ranges.IteratorAt(interval0)
    }
    has1 := interval1.Next()

    leftAside := has0 && interval0.Value.(int)+1 == val
    rightAside := has1 && interval1.Key().(int)-1 == val
    if leftAside && rightAside {
        // 情况四
        interval0.Value = interval1.Value().(int)
        ranges.Remove(interval1.Key())
    } else if leftAside {
        // 情况二
        interval0.Value = val
    } else if rightAside {
        // 情况三
        right := interval1.Value().(int)
        ranges.Remove(interval1.Key())
        ranges.Put(val, right)
    } else {
        // 情况五
        ranges.Put(val, val)
    }
}

func (ranges *SummaryRanges) GetIntervals() [][]int {
    ans := make([][]int, 0, ranges.Size())
    for it := ranges.Iterator(); it.Next(); {
        ans = append(ans, []int{it.Key().(int), it.Value().(int)})
    }
    return ans
}


/**
 * Your SummaryRanges object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddNum(val);
 * param_2 := obj.GetIntervals();
 */

python3 解法, 执行用时: 48 ms, 内存消耗: 16.5 MB, 提交时间: 2023-05-29 17:35:44

from sortedcontainers import SortedDict

class SummaryRanges:

    def __init__(self):
        self.intervals = SortedDict()

    def addNum(self, val: int) -> None:
        intervals_ = self.intervals
        keys_ = self.intervals.keys()
        values_ = self.intervals.values()

        # 找到 l1 最小的且满足 l1 > val 的区间 interval1 = [l1, r1]
        # 如果不存在这样的区间，interval1 为 len(intervals)
        interval1 = intervals_.bisect_right(val)
        # 找到 l0 最大的且满足 l0 <= val 的区间 interval0 = [l0, r0]
        # 在有序集合中，interval0 就是 interval1 的前一个区间
        # 如果不存在这样的区间，interval0 为尾迭代器
        interval0 = (len(intervals_) if interval1 == 0 else interval1 - 1)

        if interval0 != len(intervals_) and keys_[interval0] <= val <= values_[interval0]:
            # 情况一
            return
        else:
            left_aside = (interval0 != len(intervals_) and values_[interval0] + 1 == val)
            right_aside = (interval1 != len(intervals_) and keys_[interval1] - 1 == val)
            if left_aside and right_aside:
                # 情况四
                left, right = keys_[interval0], values_[interval1]
                intervals_.popitem(interval1)
                intervals_.popitem(interval0)
                intervals_[left] = right
            elif left_aside:
                # 情况二
                intervals_[keys_[interval0]] += 1
            elif right_aside:
                # 情况三
                right = values_[interval1]
                intervals_.popitem(interval1)
                intervals_[val] = right
            else:
                # 情况五
                intervals_[val] = val

    def getIntervals(self) -> List[List[int]]:
        # 这里实际上返回的是 List[Tuple[int, int]] 类型
        # 但 Python 的类型提示不是强制的，因此也可以通过
        return list(self.intervals.items())


# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(val)
# param_2 = obj.getIntervals()

javascript 解法, 执行用时: 80 ms, 内存消耗: 43.1 MB, 提交时间: 2023-05-29 17:35:09

let nums;
var SummaryRanges = function() {
    nums = new Array(10002);
};

/** 
 * @param {number} val
 * @return {void}
 */
SummaryRanges.prototype.addNum = function(val) {
    if(nums[val] === undefined)
        nums[val] = val + 1;
    finds(val);
};

/**
 * @return {number[][]}
 */
SummaryRanges.prototype.getIntervals = function() {
    let ans = new Array();
    for(let i=0;i<10001;){
        if(nums[i] != undefined){
            let tmp = new Array(2);
            tmp[0] = i;
            tmp[1] = finds(nums[i]) - 1;
            i = tmp[1] + 1;
            ans.push(tmp);
        }
        else
            i++;
    }
    return ans;
};

var finds = function(x) {
    if(nums[x] == undefined)
        return x;
    nums[x] = finds(nums[x]);
    return nums[x];
}

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * var obj = new SummaryRanges()
 * obj.addNum(val)
 * var param_2 = obj.getIntervals()
 */

java 解法, 执行用时: 18 ms, 内存消耗: 42.9 MB, 提交时间: 2023-05-29 17:34:30

class SummaryRanges {
    int[] nums;
    public SummaryRanges() {
        nums = new int[10002];
    }
    
    public void addNum(int val) {
        if(nums[val] == 0)
            nums[val] = val + 1;
        find(val);
    }
    
    public int[][] getIntervals() {
        List<int[]> ans = new ArrayList<>();
        for(int i=0;i<10001;){
            if(nums[i] != 0){
                int tmp = find(nums[i]) - 1;
                ans.add(new int[]{i, tmp});
                i = tmp + 1;
            }
            else
                i++;
        }
        int[][] res = new int[ans.size()][2];
        int idx = 0;
        for(int[] data:ans){
            res[idx][0] = data[0];
            res[idx++][1] = data[1];
        }
        return res;
    }

    private int find(int x){
        if(nums[x] == 0)
            return x;
        nums[x] = find(nums[x]);
        return nums[x];
    }
}

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(val);
 * int[][] param_2 = obj.getIntervals();
 */

python3 解法, 执行用时: 36 ms, 内存消耗: 17.2 MB, 提交时间: 2023-05-29 17:34:13

# 并查集
from sortedcontainers import SortedSet
class SummaryRanges:

    def __init__(self):
        self.find = [i for i in range(10002)]
        self.points = SortedSet()

    def addNum(self, val: int) -> None:
        self.points.add(val)
        self.find[val] = self.find[val + 1]

    def getIntervals(self) -> List[List[int]]:
        ans = []
        for p in self.points:
            if ans and p <= ans[-1][1]:
                continue
            ans.append([p, self.f(p) - 1])
        return ans
    
    def f(self, x):
        if x == self.find[x]:
            return x
        self.find[x] = self.f(self.find[x])
        return self.find[x]


# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(val)
# param_2 = obj.getIntervals()

上一题

下一题

详情