有一组元素,不断被动态添加和删除数据,找出每一组的中位数
时间: 2024-06-06 11:11:28 浏览: 9
解决这个问题可以使用堆来实现。堆是一种数据结构,可以快速找到最大值或最小值,而且在插入或删除元素时也可以很快地调整堆的结构。
具体的做法是,我们可以用一个小根堆来存储较大的一半数,一个大根堆来存储较小的一半数。由于堆的性质,小根堆的堆顶元素一定是较大数中最小的,大根堆的堆顶元素一定是较小数中最大的。因此,中位数就可以通过堆顶元素计算得到。
当新加入一个数时,我们可以将其与小根堆和大根堆的堆顶元素进行比较。如果小于等于大根堆的堆顶元素,则加入大根堆;否则加入小根堆。然后我们需要保证两个堆的元素个数平衡,即小根堆元素个数等于大根堆元素个数或多一个。如果两个堆的元素个数不平衡,我们就需要进行调整,将多余的元素从一个堆中弹出,加入到另一个堆中。
以下是 Python 代码实现:
import heapq
class MedianFinder:
def __init__(self):
"""
initialize your data structure here.
"""
self.min_heap = [] # 小根堆
self.max_heap = [] # 大根堆
def addNum(self, num: int) -> None:
if not self.max_heap or num <= -self.max_heap[0]:
# 加入大根堆
heapq.heappush(self.max_heap, -num)
if len(self.max_heap) > len(self.min_heap) + 1:
# 调整堆大小
heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
else:
# 加入小根堆
heapq.heappush(self.min_heap, num)
if len(self.min_heap) > len(self.max_heap):
# 调整堆大小
heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
def findMedian(self) -> float:
if len(self.max_heap) == len(self.min_heap):
return (-self.max_heap[0] + self.min_heap[0]) / 2
else:
return -self.max_heap[0]
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)