Posted on 2022-11-12 17:57
Uriel 閱讀(65)
評論(0) 編輯 收藏 引用 所屬分類:
閑來無事重切Leet Code 、
二分.三分
有兩種操作，1.向一堆數(shù)字中增加一個數(shù)，2.或者查詢目前已有的這堆數(shù)的中位數(shù)是多少，一共可能有50000次請求
方法一：每次增加一個數(shù)的時候用二分查找然后插入，查詢的時候分數(shù)列有奇數(shù)或者偶數(shù)個數(shù)字分類輸出
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