Shauby

分类

/ 注册

全部文章（共4篇）

题解 | #数据流中的中位数#

从零开始实现堆，获取数据流中的中位数。中位数可能由两位数决定，所以需要两个堆。中位数特点：对于排好序的序列，它是左半部分的最大值，是右半部分的最小值。当元素个数是偶数时，左右半部分元素个数相等，中位数是左边最大和右边最小的平均，当元素个数是奇数时，让左半部分多一个元素，那么中位数就是左半部分...

数组堆(优先队列) Python3

2022-08-08

0 241

题解 | #寻找第K大#

时间复杂度O(nlogk)，空间复杂度O(1)。用类似寻找k个最大数的思路，在原列表上维护一个长度为k的小根堆。遍历列表a[K:]，如果存在比堆里元素大的值（只要比堆顶元素（最小值）大），就换掉原堆顶，然后调整堆。遍历完列表之后，长度为k的堆内的值均不小于外部的值，且堆顶为堆...

数组堆(优先队列) Python3

2022-08-08

0 268

题解 | #最小的K个数#

堆排序实现最小k个数 class Solution: # 小根堆调整函数，静态方法 @staticmethod def h...

堆(优先队列) 数组 Python3

2022-08-07

0 243

题解 | #滑动窗口的最大值#

从零开始，用堆实现求滑动窗口最大值。通过维护一个大堆来获取最大值及其下标。遇到一个值就加入堆，在新添加元素后，如果堆顶元素的下标还在滑动窗口范围内，则获取其值。否则弹出堆顶元素，至堆顶元素的下标在滑动窗口范围内。 class Solution: &n...

Python3 堆(优先队列)

2022-08-07

0 273