首先将数组nums进行排序,然后找到中间位置的数值
如果数组长度n为奇数,则(n+1)/2处对应值为中位数,如果数组下标从0开始,还需要减去1
如果数组长度n为偶数,则n/2,n/2+1两个位置数的平均值为中位数
假设中位数为x,并采用大小根堆来存储元素
- 采用大根堆存储小于等于中位数的元素,记大根堆的长度为 n m a x n_{max} nmax
- 采用小根堆存储大于中位数的元素,记小根堆的长度为 n m i n n_{min} nmin
- 保持
n
m
i
n
≤
n
m
a
x
≤
n
m
i
n
+
1
n_{min}\le n_{max}\le n_{min}+1
nmin≤nmax≤nmin+1
在遍历数组num的过程中,维持以上三个条件,即确保大根堆的堆顶元素必为中位数,那么
- 当 n u m ≤ x num\le x num≤x时,将num推入que_max中,同时比较大小根堆的长度,当 n m a x > n m i n + 1 n_{max}>n_{min}+1 nmax>nmin+1,表明新的中位数小于原来的中位数,则将que_max中堆顶元素弹出,并推入到小根堆que_min中
- 当 n u m > x num> x num>x时,将num推入que_minx中,同时比较大小根堆的长度,当 n m a x < n m i n n_{max}<n_{min} nmax<nmin,表明新的中位数大于原来的中位数,则将que_min中堆顶元素弹出,并推入到大根堆 q u e m a x que_max quemax中
import numpy as np
import heapq
nums = np.random.choice(np.array(20),10,replace=False)
print('数组为',nums)
def findmid(nums):
que_min = list() #小根堆,存储大于中位数的元素
que_max = list() #大根堆,存储小于等于中位数的元素 !python中默认建造小根堆,可以将元素进行取负,来构造大根堆
n = len(nums)
for i in range(n):
if not que_max or nums[i] <= -que_max[0]:
heapq.heappush(que_max,-nums[i])
if len(que_max) > len(que_min)+1:
heapq.heappush(que_min,-que_max[0])
heapq.heappop(que_max)
else:
heapq.heappush(que_min, nums[i])
if len(que_min) > len(que_max):
heapq.heappush(que_max,-que_min[0])
heapq.heappop(que_min)
if n % 2==0:
return (que_min[0] - que_max[0])/2
else:
return que_max[0]
print('数组的中位数为:',findmid(nums))
输出结果如下: