Ano*_*ous 12 sorting algorithm search nearest-neighbor median
我可以使用中位数选择算法的中位数来找出O(n)中的中位数.此外,我知道在算法完成后,中位数左边的所有元素都小于中位数,右边的所有元素都大于中位数.但是如何在O(n)时间内找到k个最近邻居的中位数呢？
如果中位数是n,则左边的数字小于n,右边的数字大于n.但是,数组未在左侧或右侧排序.数字是用户给出的任何一组不同的数字.
问题来自Cormen的算法导论,问题9.3-7
小智 18
似乎没有人有这个.这是怎么做的.首先,如上所述找到中值.这是O(n).现在将中位数停在数组的末尾,并从每个其他元素中减去中位数.现在再次使用快速选择算法找到数组的元素k(不包括最后一个元素).这不仅找到元素k(按顺序),它还离开数组,使得最低的k数位于数组的开头.一旦你将中位数加回来,这些是最接近中位数的k.
中位数的中位数可能对寻找最近的邻居没有太大帮助,至少对于大的n来说.没错,你有5列的每一列都是以中位数划分的,但这并不足以解决问题.
我只是将中位数视为中间结果,并将最近邻居视为优先队列问题......
一旦你得到中位数中位数的中位数,记下它的值.
对所有数据运行heapify算法 - 请参阅Wikipedia - Binary Heap.在比较中,将结果基于相对于保存的中值的差异.优先级最高的项目是ABS(值 - 中位数)最低的项目.这需要O(n).
数组中的第一项现在是中位数(或它的副本),并且数组具有堆结构.使用堆提取算法根据需要提取尽可能多的最近邻居.对于k个最近邻居,这是O(k log n).
只要k是一个常数,你得到中位数的O(n)中位数,O(n)heapify和O(log n)提取,总得O(n).
事实上，答案很简单。我们需要做的就是当中位数位于索引 m 时，从 m-1 到 0 以及 m+1 到 n-1 中选择与中位数绝对差最小的 k 个元素。我们使用与合并 2 个排序数组相同的想法来选择元素。