中间60%的k window之和

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

关于双倍积分奖励算法题和系统设计题讨论的决定：

我们：
1. 希望能看到干货讨论；
2. 希望能看到好的代码（web端高级发帖模式下，@ 朋友右边的<> 可以选择多种代码）

版主 @14417335 负责审核加分，也请大家给好的回复加分 + 顶。
大家给30，我会跟进奖励30，double之；
大家给100，我也会跟进奖励100，double之。

很理解大家写代码、调试、写思路分析，很花时间。对于特别好的回复，还会有额外加分。

欢迎大家拿出好的题目讨论，选中了我会全站置顶。哪位同学起了好的题目/帖子，激发了干货讨论，也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复，也请大家顶一下，作为对别人积极参与讨论、热心分享的认可和鼓励。
其他可以获得双倍积分的题目：

在刷题版里选择高频题标签，版主@14417335 发的所有帖子，链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019
大家看到LC没有的高频题，也请贴到刷题版里，又有大米又有赞。对于学弟学妹们也是功劳一件。举手之劳。谢谢大家的参与。

这题参照 Sliding Window Median，题目用了一个maxheap, 一个minheap分别维护 k/ 2, k - k/2个数。我们将其扩展为HeapX。
class HeapX(k, x)。表示维护 前x*k 和 k-x*k个数。
那么这题就是维护两个HeapX，pq1=HeapX(k, x), pq2=HeapX(k, 1 - x)。那么sum（中间k - 2 * k *x个数 ）= sum(pq1.minheap) - sum(pq2.minheap)。其中求sum可以用一个变量缓存，达到O(1)，最后理论上复杂度可以变成O(nlogk)

umialpha 发表于 2019-4-6 15:46
这题参照 Sliding Window Median，题目用了一个maxheap, 一个minheap分别维护 k/ 2, k - k/2个数。我们将其 ...

这个方法感觉是nklog(k)呀

这个题最近面经里面看到好几次：

您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2019-5-28 22:52):
感觉java和c++都还好，可以用treeset。主要是python
比较坑。。。

步惊云 发表于 2019-3-7 13:39
这可太segment tree了

请问用segment tree怎么解

blackarrow3542 发表于 2019-5-28 22:53
请问用segment tree怎么解

感觉segment tree或者Fenwick Tree可能是nlogn*logn?

blackarrow3542 发表于 2019-5-28 23:48
感觉segment tree或者Fenwick Tree可能是nlogn*logn?

随便搜了一下，发现也有针对stream的segment tree, 不过估计现场不太好想。
也许multiset能做？维护两个iterator分别指向中间段的两端，然后根据iterator的移动方向update sum值，跟sliding window median的解法类似。