Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2022-11-13 00:36:09
295. Find Median from Data Stream
实作一个资料结构,需实现两种操作:
1.addNum(int n)
把一个资料加入流
2.findMedian()
从资料流里面取出一个数字,若:
* 资料有偶数个:返回大小最接近中间的两数字,并相加除二
* 资料有奇数个:返回大小排序后刚好在正中间的数字
思路:
1.插入一个元素到List并排序他,直接排序整个List不意外吃了TLE,改用binary
search来找插入元素的位置,这样时间复杂度从O(nlogn)变成O(n),勉勉强强AC了。
(如果不存在数字,binarySearch返回的是负数的该元素应插入位置)
2.判断list的size来决定是要返回中间元素还是左右相加除二。
Java Code:
作者: fxfxxxfxx (爱丽丝)   2022-11-13 00:51:00
这题应该会希望做到单次 O(logn)用两个heap可以做到 addNum O(logn), findMedian O(1)不过我也是看别人答案才知道的 有点难想
楼主: Rushia (みけねこ的鼻屎)   2022-11-13 00:54:00
这个HEAP用法真的满厉害的
作者: GTR12534 (カラス)   2022-11-13 03:27:00
Pythonista 当然是直接 SortedList 干下去

Links booklink

Contact Us: admin [ a t ] ucptt.com