[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

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
# 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%的提交。