本文共 2197 字，大约阅读时间需要 7 分钟。

Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:

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

Follow up:

What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?

Accepted

29,659

Submissions

65,681

---------------------------------------------------------------------------------------------------------------------------------------

这题二分法很容易想到，问题是找到插入位置后还要进行O(n)的移动，这点不确定，看了一下别人的题解，好像这个移动都做了，所以就跟着往下做了。。。

这题能一次提交通过主要感谢自己在  的总结，二分退出来，二分的范围是[0,l]闭区间，有了这点，分别讨论四种情况：和左边在一起，和右边在一起，merge，插入，最终codes是，遗憾的是自己在Pycharm里居然写了俩bug，不应该啊：

class SummaryRanges:    def __init__(self):        """        Initialize your data structure here.        """        self.segs = []    def addNum(self, val):        l = len(self.segs)        left, right = 0, l - 1        while (left <= right):            mid = left + ((right - left) >> 1) #bug1: mid = left + ((right - left) >> 1)            if (self.segs[mid][0] <= val): #bug2: self.segs[mid][0] >= val                left = mid + 1            else:                right = mid - 1        # merge        if (left - 1 >= 0 and left < l and self.segs[left - 1][1] + 1 == self.segs[left][0] - 1 and self.segs[left - 1][1] + 1 == val):            self.segs[left - 1][1] = self.segs[left][1]            self.segs.pop(left)        elif (left - 1 >= 0 and self.segs[left - 1][1] + 1 == val): #放左边            self.segs[left - 1][1] = val        elif (left < l and self.segs[left][0] - 1 == val): #放右边            self.segs[left][0] = val        elif ((left - 1 >= 0 and self.segs[left - 1][1] + 1 < val) or left == 0): #必须插入            self.segs.insert(left, [val, val])    def getIntervals(self):        return self.segs# Your SummaryRanges object will be instantiated and called as such:obj = SummaryRanges()obj.addNum(1)print(obj.getIntervals())obj.addNum(3)print(obj.getIntervals())obj.addNum(7)print(obj.getIntervals())obj.addNum(2)print(obj.getIntervals())obj.addNum(6)print(obj.getIntervals())

转载地址：http://jtfoi.baihongyu.com/