algorithm - 如何在 O(n) 时间内找到 n 个不同数字的中位数的 k 个最近邻居？

Question

我可以使用中位数选择算法在 O(n) 中找到中位数。另外，我知道算法完成后，中位数左侧的所有元素都小于中位数，而右侧的所有元素都大于中位数。但是如何在 O(n) 时间内找到距离中位数最近的 k 个邻居？

如果中位数为n，则左边数小于n，右边数大于n。但是，数组未按左侧或右侧排序。这些数字是用户给出的任何一组不同的数字。

问题来自 Cormen 的 Introduction to Algorithms，问题 9.3-7

Answer 1

似乎没有人完全掌握这一点。这是如何做的。首先，如上所述找到中位数。这是 O(n)。现在将中位数放在数组的末尾，并从每个其他元素中减去中位数。现在找到数组的元素 k(不包括最后一个元素)，再次使用快速选择算法。这不仅找到元素 k(按顺序)，它还离开数组，以便最小的 k 数字位于数组的开头。一旦您重新添加中位数，这些就是最接近中位数的 k。