- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我正在尝试返回一系列流媒体数字的运行中位数。为此,我使用最大堆(将值存储在序列的下半部分)和最小堆(将值存储在序列的上半部分)。
特别是我使用 heapq 模块 ( https://docs.python.org/2/library/heapq.html ) 中的 Python (2.0) 内置最小堆数据结构。为了构建最大堆,我只需使用我需要插入堆中的数字的负数。
我的 Python 代码如下:
import heapq
maxh = []
minh = []
vals=[1,2,3,4,5,6,7,8,9,10]
for val in vals:
# Initialize the data-structure and insert/push the 1st streaming value
if not maxh and not minh:
heapq.heappush(maxh,-val)
print float(val)
elif maxh:
# Insert/push the other streaming values
if val>-maxh[0]:
heapq.heappush(minh,val)
elif val<-maxh[0]:
heapq.heappush(maxh,-val)
# Calculate the median
if len(maxh)==len(minh):
print float(-maxh[0]+minh[0])/2
elif len(maxh)==len(minh)+1:
print float(-maxh[0])
elif len(minh)==len(maxh)+1:
print float(minh[0])
# If min-heap and max-heap grow unbalanced we rebalance them by
# removing/popping one element from a heap and inserting/pushing
# it into the other heap, then we calculate the median
elif len(minh)==len(maxh)+2:
heapq.heappush(maxh,-heapq.heappop(minh))
print float(-maxh[0]+minh[0])/2
elif len(maxh)==len(minh)+2:
heapq.heappush(minh,-heapq.heappop(maxh))
print float(-maxh[0]+minh[0])/2
下面是我为检查我的代码而构建的测试用例的完整列表:
vals=[1,2,3,4,5,6,7,8,9,10] # positive numbers, increasing series
vals=[10,9,8,7,6,5,4,3,2,1] # positive numbers, decreasing series
vals=[10,9,11,8,12,7,13,6,14,5] # positive numbers, jumping series (keeping
# heaps balanced)
vals=[-10,-9,-8,-7,-6,-5,-4,-3,-2,-1] # negative numbers, increasing series
vals=[-1,-2,-3,-4,-5,-6,-7,-8,-9,-10] # negative numbers, decreasing series
vals=[-10,-9,-11,-8,-12,-7,-13,-6,-14,-5] # negative numbers
# jumping series (keeping heaps
# balanced)
vals=[-5,-4,-3,-2,-1,0,1,2,3,4,5] # mixed positive-negative numbers,
# increasing series
vals=[5,4,3,2,1,0,-1,-2,-3,-4,-5] # mixed positive-negative numbers,
# decreasing series
vals=[0,-1,1,-2,2,-3,3,-4,4,-5,5] # mixed positive-negative numbers,
# jumping series (keeping heaps balanced)
我的代码对我来说似乎没问题,但我无法通过在线评判 (https://www.hackerrank.com/challenges/ctci-find-the-running-median/problem) 的 10 个测试用例中的 4 个。
你有什么提示吗?
最佳答案
问题出在这里:
# Insert/push the other streaming values
if val>-maxh[0]:
heapq.heappush(minh,val)
elif val<-maxh[0]:
heapq.heappush(maxh,-val)
如果 val == maxh[0]
,则该项目永远不会被插入任一堆。您应该能够通过测试用例 [1,1,2]
揭示错误。
一个简单的修复方法是:
# Insert/push the other streaming values
if val >= -maxh[0]:
heapq.heappush(minh,val)
else
heapq.heappush(maxh,-val)
关于Python:使用 Max-Heap 和 Min-Heap 查找运行中位数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45482156/
我正在分析一个显示一些奇怪的转储:命令 !heap -x -v hexadecimal_address 之间似乎存在矛盾。和 !heap -flt s size_of_block 我正在询问悬空指针。
我试图找到免费商店通常被称为堆的官方(或足够好的)原因。 除了它从数据段的末尾增长这一事实之外,我真的想不出一个很好的理由,尤其是因为它与堆数据结构几乎没有关系。 注意:很多人提到它只是一堆无组织的东
我发现了很多 MinMax Heap 实现,它们将数据存储在一个数组中。这真的很容易实现,这就是我正在寻找不同的东西的方式。我想创建一个 MinMax 堆,只使用堆的元素和指向左 child 和右 c
Ehcache talks about堆内和堆外内存。有什么不同?使用哪些 JVM 参数来配置它们? 最佳答案 堆上存储是指将出现在 Java 堆中的对象(并且也会受到 GC)。另一方面,堆外存储是指
多年来,我一直将 !heap –p –a 用于各种任务。 现在我开始使用最新的 Win8 sdk 中的 WinDbg 6.2.9200 在 Win8 上进行调试。 在这里,我发现 !heap –p –
我试图确定为什么我的应用程序消耗 4GB 的私有(private)字节。所以我做了一个完整的内存转储,将它加载到windbg中。但是使用 !heap -stat -h 进行分析产生不加起来的奇怪结果:
我正在分析 native 内存泄漏的转储,然后我观察到“锁争用”在 !heap –s 输出中。我不记得以前见过这个。这是什么意思? 最佳答案 这是堆管理器的锁争用。高锁争用通常是由大量并发分配请求引起
突然我的应用程序崩溃并弹出这个错误...知道这个错误吗?千辛万苦还是解决不了... 将目标 GC 堆从 111MB 钳制到 96MB Alloc 并发标记扫描 GC 释放了 3(96B) 个 Allo
我需要在应用程序运行时监控 JVM 空间,我使用 JMC 进行监控,但是当我停止 tomcat 时,JMC 不工作。 我的目标是我需要验证当应用程序关闭时所有堆内存(或某些部分)是否被释放以及它释放了
我有一个内存转储。在这个转储中,我有一个句柄为 fd00000 的堆。这是 !heap -s fd00000 命令输出的摘录: 0: Heap 0fd00000 Flags 00
我正在尝试返回一系列流媒体数字的运行中位数。为此,我使用最大堆(将值存储在序列的下半部分)和最小堆(将值存储在序列的上半部分)。 特别是我使用 heapq 模块 ( https://docs.pyth
我知道 Android 平台中有 Dalvik(JVM) 堆和 native 堆。而且 Dalvik GC 在 native 堆上没有工作。但我不确定这是如何工作的,我的意思是 Android 操作系
-Xms是指定初始堆大小还是最小堆大小?我看到不同的观点。有些人喜欢 second answer here ,说它用于初始堆,而其他一些人说它是最小堆大小。 还是说最小尺寸本身就是初始尺寸? 最佳答案
我正在编写一个将大量联系人与 Android 联系人数据库同步的程序。对于大约 700 个联系人,下载工作正常,之后我不断收到内存堆错误,该错误调用无限数量的 GC 语句并最终重新启动手机。我正面临
我正在使用 Apache Ignite ver2.7,使用 Config.xml 设置启动 Ignite 服务器。 ./ignite.sh $IGNITE_HOME/config/config.xml
在 Eclipse IDE 中执行 Web 驱动程序脚本时,出现 Unable to execute dex: Java heap space Java heap space 错误。我已经用 Andr
我有一个带有以下参数的 Java 应用程序,但即使总可用空间大于 45%(可以通过可视化 VM 看到),堆也不会被回收。 JVM 是否有任何理由不释放该堆空间?相同的设置在 Java6 中按预期工作。
我正在查看 ASP.NET 4 应用程序(工作流服务)的性能计数器 .NET CLR Memory -- # Bytes in all Heaps : 44,420,488 .NET CLR M
CentOS Linux 发行版 7.3.1611 gcc 版本 4.8.5 20150623 gperftool 2.4-8.el7 1.my c++ 程序链接 -ltcmalloc 在没有 HEA
我创建了一个Gradle包装器 $ gradle wrapper --gradle-version 5.0 --distribution-type all ...现在有 $ ./gradlew -ve
我是一名优秀的程序员,十分优秀!