如何找到k近邻到n个不同的数字在O（n）时间的中位数？ [英] How to find k nearest neighbors to the median of n distinct numbers in O(n) time?
问题描述
我可以使用的中位数选择算法中位数找到O（n）的中位数。另外，我知道该算法完成之后，所有元素的位数左边是少的位数和所有元素向右大于中值。但我怎么找到k个最近邻中位数为O（n）的时间？
I can use the median of medians selection algorithm to find the median in O(n). Also, I know that after the algorithm is done, all the elements to the left of the median are less that the median and all the elements to the right are greater than the median. But how do I find the k nearest neighbors to the median in O(n) time?
如果位数为n，数到左边是小于n和数字，右边是大于n。 然而，该阵列未在左侧或右侧排序。这些数字是任意一组由用户给定的不同的数字。
If the median is n, the numbers to the left are less than n and the numbers to the right are greater than n. However, the array is not sorted in the left or the right sides. The numbers are any set of distinct numbers given by the user.
现在的问题是，从算法导论由Cormen，问题9.3-7
The problem is from Introduction to Algorithms by Cormen, problem 9.3-7
推荐答案
其实，答案是pretty的简单。所有我们需要做的是选择k个元素与中位数从M-1移动到0和M + 1到n-1时，中位数为指数M最小的绝对差值。我们选择使用我们合并2排序数组使用相同的想法的元素。
Actually, the answer is pretty simple. All we need to do is to select k elements with the smallest absolute differences from the median moving from m-1 to 0 and m+1 to n-1 when the median is at index m. We select the elements using the same idea we use in merging 2 sorted arrays.
这篇关于如何找到k近邻到n个不同的数字在O（n）时间的中位数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
