我遇到了这个问题: 实现一个队列,其中push_rear(),pop_front()和get_min()都是常量时间操作.
我最初想过使用一个最小堆数据结构,它对于get_min()具有O(1)复杂度.但是push_rear()和pop_front()将是O(log(n)).
有谁知道实现这样一个有O(1)push(),pop()和min()的队列的最佳方法是什么？
我搜索了这个,并想指出这个算法极客线程.但似乎没有一个解决方案遵循所有3种方法的恒定时间规则:push(),pop()和min().
感谢所有的建议.
我有一个(大)数值数据(大小)数组,N并希望计算一个具有固定窗口大小的运行最大值的数组w.
更直接的是,我可以out[k-w+1] = max{data[k-w+1,...,k]}为k >= w-1(定义基于0的数组,如在C++中)定义一个新数组.
有没有更好的方法来做到这一点N log(w)？
[我希望在N没有依赖的情况下应该有一个线性的w,比如移动平均线,但找不到它.对于N log(w)我认为有一个排序的数据结构,它会做管理的方式insert(),delete()并extract_max()完全在log(w)以下大小的结构w-就像一个排序二叉树,例如.
非常感谢你.
最近我陷入了困境.算法部分需要计算长度为K的滑动窗口的最大元素之和.其中K的范围是1 <= K <= N(阵列的N长度).
示例如果我有一个数组A作为5,3,12,4
长度为1的5 + 3 + 12 + 4 = 24
滑动窗口:长度为2的5 + 12 + 12 = 29
滑动窗口:长度为3的12 + 12 = 24
滑动窗口:长度为4的滑动窗口:12
Final answer is 24,29,24,12.
我试过这个O(N ^ 2).对于长度为K的每个滑动窗口,我可以用O(N)计算最大值.由于K高达N.因此,总体复杂度变为O(N ^ 2).
我正在寻找O(N)或O(NlogN)或与此算法类似的东西,因为N可能高达10 ^ 5.
注意:数组中的元素可以大到10 ^ 9,因此输出最终答案为模10 ^ 9 + 7
编辑:我实际上想要找到K的每个值(即从0到N)的答案线性时间或O(NlogN)不在O(KN)或O(KNlogN)中,其中K = {1,2,3,...... N}