Posted on 2022-11-12 17:57
Uriel 阅读(58)
评论(0) 编辑 收藏 引用 所属分类:
闲来无事重切Leet Code 、
二分.三分
有两种操作，1.向一堆数字中增加一个数，2.或者查询目前已有的这堆数的中位数是多少，一共可能有50000次请求
方法一：每次增加一个数的时候用二分查找然后插入，查询的时候分数列有奇数或者偶数个数字分类输出
1 #295
2 #Runtime: 3677 ms
3 #Memory Usage: 38 MB
4
5 class MedianFinder(object):
6
7 def __init__(self):
8 self.nums = []
9
10
11 def addNum(self, num):
12 """
13 :type num: int
14 :rtype: None
15 """
16 if not self.nums:
17 self.nums.append(num)
18 return
19 l = 0
20 r = len(self.nums)
21 while l < r:
22 mid = int((l + r) / 2)
23 if self.nums[mid] < num:
24 l = mid + 1
25 else:
26 r = mid
27 self.nums.insert(l, num)
28 return
29
30
31 def findMedian(self):
32 """
33 :rtype: float
34 """
35 if len(self.nums) % 2:
36 return self.nums[len(self.nums) // 2]
37 else:
38 return (self.nums[len(self.nums) // 2] + self.nums[len(self.nums) // 2 - 1]) / 2.0
方法二：用Python的SortedList
1 #295
2 #Runtime: 742 ms
3 #Memory Usage: 38.6 MB
4
5 from sortedcontainers import SortedList
6
7 class MedianFinder(object):
8
9 def __init__(self):
10 self.nums = SortedList()
11
12
13 def addNum(self, num):
14 """
15 :type num: int
16 :rtype: None
17 """
18 self.nums.add(num)
19 return
20
21
22 def findMedian(self):
23 """
24 :rtype: float
25 """
26 if len(self.nums) % 2:
27 return self.nums[len(self.nums) // 2]
28 else:
29 return (self.nums[len(self.nums) // 2] + self.nums[len(self.nums) // 2 - 1]) / 2.0