[leetcode 352]原创解法

题目概述

原题链接

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]

解题思路

断断续续思考了一段时间。naive的想法考虑了以下几点，

1. 一个list存放interval，然后遍历。
2. 需要查比邻的interval的值，因为需要合并。
3. 需要插入新的interval

从这几点首先想到用二叉搜索树来存放interval，这样既能快速查到，又能保证有序， 但是实现起来的时候，发现有两个问题，

1. 合并节点非常复杂（其实可以做到）
2. 简单的二叉搜索树无法保证是平衡树（这个非常影响性能）

最后考虑的结果是这样的，

1. 用list存放有序的interval
2. 使用二分查找保证快速找到最近的interval
3. 合并interval的时候比较简单快速。

一遍通过的解法

编码的过程，比较慢，写了快一个小时，因为要仔细考虑边界值的问题， 但是一遍就通过了测试，比较开心，毕竟该题号称hard。

# Definition for an interval.
class Interval(object):
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e

    def __repr__(self):
        return "[{},{}]".format(self.start, self.end)


def nearest(arr, val):
    """
    返回最接近的interval的索引
    :param arr:
    :param val:
    :return:
    """
    start = 0
    end = len(arr) - 1
    mid = int((start + end) / 2)
    while start < end:
        item = arr[mid]
        if item.start - 1 <= val <= item.end + 1:
            return mid
        elif val < item.start - 1:
            end = mid
        elif val > item.end + 1:
            if start == mid:
                start = mid + 1
            else:
                start = mid

        mid = int((start + end) / 2)
    return mid


class SummaryRanges(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.arr = []

    def addNum(self, val):
        """
        :type val: int
        :rtype: void
        """
        if len(self.arr) == 0:
            interval = Interval(val, val)
            self.arr.append(interval)
        else:
            i = nearest(self.arr, val)
            item = self.arr[i]
            if item.start <= val <= item.end:
                return
            elif val == item.start - 1:
                item.start = val
                while i > 0 and self.arr[i - 1].end == item.start - 1:
                    self.arr[i - 1].end = item.end
                    self.arr.pop(i)
                    item = self.arr[i - 1]
                    i = i - 1
            elif val == item.end + 1:
                item.end = val
                while i < len(self.arr) - 1 and self.arr[i + 1].start == item.end + 1:
                    item.end = self.arr[i + 1].end
                    self.arr.pop(i + 1)
            elif val < item.start - 1:
                interval = Interval(val, val)
                self.arr.insert(i, interval)
            elif val > item.end + 1:
                interval = Interval(val, val)
                self.arr.insert(i + 1, interval)

    def getIntervals(self):
        """
        :rtype: List[Interval]
        """
        return self.arr


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

if __name__ == '__main__':
    obj = SummaryRanges()
    obj.addNum(1)
    print(obj.getIntervals())  # [1,1]
    obj.addNum(3)
    print(obj.getIntervals())  # [1,1],[3,3]
    obj.addNum(7)
    print(obj.getIntervals())  # [1,1],[3,3],[7,7]
    obj.addNum(2)
    print(obj.getIntervals())  # [1,3],[7,7]
    obj.addNum(6)
    print(obj.getIntervals())  # [1,3],[6,7]

高效的Python List

我一开始不愿意使用list的本质原因是需要在List的中间删除和插入数据，因为 对于一个size为n的list，list.pop(0)的时间复杂度是O(n)。 但是Python的List似乎仍然非常高效，即使在list中间删除和插入数。我本来以为 我的这个解法会超时呢，结果居然击败的80%的提交。