算法 – 跟踪扩展阵列的中位数
发布时间：2020-12-14 16:44:05 所属栏目：Java 来源：网络整理
导读：面试问题： 下面编辑 给你一个数组.你做出2堆,一个minheap和另一个最大堆.现在使用O(nlog n)时间的这两个提供的堆,找到数组的中位数. 更正问题 数字随机生成并存储到(扩展)数组中.你如何跟踪中位数？ 解 这个问题可以使用2堆来解决,而且中等值可以在O(1)时间
|
面试问题：
下面编辑 更正问题 解 解决方法
以下是您如何使用这两个堆.注意,我假设你不知道元素的数量,这就是为什么我们必须弹出,直到我们从最小堆中弹出大于或等于我们从最大堆中弹出的东西.注意,我们返回平均值,因为在{1,2,3,4}的集合的情况下,中位数实际上是2.5(两个“中间”值的平均值).我假设价值类型是双重的,但这显然是任何事情.这里：
double min = minheap.pop();
double max = maxheap.pop();
while(min < max) {
min = minheap.pop();
max = maxheap.pop();
}
return (min + max) / 2;
因为弹出是O(log n),我们必须弹出O(n / 2)值,这是O(n log n). （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |