我遇到了这个问题: 实现一个队列,其中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().
感谢所有的建议.
我有一个类似的阵列
[5.5, 6.0, 6.0, 6.5, 6.0, 5.5, 5.5, 5.0, 4.5].
该数组的所有数字相差0.5,两个连续数字的最大差值也为0.5(它们可以相同;如示例中所示).并且有一个移动间隔或框,其中包含例如3个连续数字,如下所示:
[(5.5, 6.0, 6.0), 6.5, 6.0, 5.5, 5.5, 5.0, 4.5] # min: 5.5, max: 6.0
并且盒子一个接一个地向右移动:
[5.5, (6.0, 6.0, 6.5), 6.0, 5.5, 5.5, 5.0, 4.5] # min: 6.0, max: 6.5
[5.5, 6.0, (6.0, 6.5, 6.0), 5.5, 5.5, 5.0, 4.5] # min: 6.0, max: 6.5
问题是,如何在每个时间框移动时找到框内数字的最小值和最大值？
当盒子和数组的大小像这个例子那样小时,我可以处理它,但我需要将它应用于数组大小100000和盒子大小10000.使用我的方法(我每次使用for循环计算每个max和min盒子通过),花了太多时间(我有100多个阵列要做,需要反复运行).有一些时间限制,所以我需要在0.5秒内像一次计算一样运行它.
给定一个整数数组和一个整数值K我的任务是编写一个函数,该函数将标准输出中的该值的最大数字和之前的K个条目打印到标准输出.
示例输入:
tps: 6, 9, 4, 7, 4, 1
k: 3
示例输出:
6
9
9
9
7
7
有人告诉我,我编写的代码可以更有效地用于大型数据集.如何才能使此代码最有效？
def tweets_per_second(tps, k):
past = [tps[0]]
for t in tps[1:]:
past.append(t)
if len(past) > k: past = past[-k:]
print max(past)