我相信有一种方法可以在O(n)中找到长度为n的未排序数组中的第k个最大元素.或许它是"预期的"O(n)或其他东西.我们应该怎么做？
这是众所周知的选择算法.见http://en.wikipedia.org/wiki/Selection_algorithm.
我需要它来找到一组3x3x3体素值的中值.由于体积由十亿个体素组成,算法是递归的,因此最好快一点.通常可以预期值相对接近.
到目前为止,我尝试过的最快的已知算法使用了快速排序分区功能.我想知道是否有更快的.
我已经"发明"了使用两个堆的速度提高了20%,但预计使用散列会更快.在实现这个之前,我想知道是否已经存在闪电战快速解决方案.
我使用浮点数的事实应该无关紧要,因为它们在反转符号位后可以被认为是无符号整数.订单将被保留.
编辑:基准和源代码按照Davy Landman的建议转移到单独的答案中.请参阅下面的chmike答案.
编辑:迄今为止最有效的算法被Boojum引用作为Fast Median和双边过滤论文的链接,现在这个问题的答案就是答案.这种方法的第一个聪明的想法是使用基数排序,第二个是组合共享大量像素的相邻像素的中值搜索.
我只是遇到了一个问题,给我带来了困难,我仍在努力弄清楚如何满足空间和时间复杂性的限制.
问题如下:数组中的主要成员是占据阵列中一半以上位置的成员,例如:
{3,67,23,67,67}
67是主导成员,因为它在阵列中出现在3/5(> 50%)位置.
现在,您需要提供一个接收数组的方法,如果存在,则返回显性成员的索引,如果没有,则返回-1.
容易,对吗？好吧,如果不是因为以下限制,我可以轻松地解决问题:
我可以看到你如何用O(n)空间复杂度来解决这个问题,以及O(1)空间复杂度的O(n ^ 2)时间,但不能满足O(n)时间和O(1)空间.
我真的很感激能够找到解决这个问题的方法.别担心,截止日期已经过了几个小时(我只有30分钟),所以我不是想欺骗.谢谢.
给定一个未排序的整数序列,它作为流流入您的程序.
整数太多,不适合记忆.
想象一下有一个功能:
int getNext() throws NoSuchElementException;
它返回流中的下一个整数.
写一个函数来找到中位数.
解决O(n)中的问题.
有任何想法吗？
给出提示(使用堆数据结构..)
例如,给定N个元素的无序列表,找到子范围0..100,25..200,400..1000,10..500的中位数......我没有看到比通过每个元素更好的方法子范围并运行标准中位数查找算法.
一个简单的例子:[5 3 6 2 4] 0..3的中位数是5.(不是4,因为我们询问原始列表的前三个元素的中位数)