我可以使用中位数选择算法在 O(n) 中找到中位数。另外,我知道算法完成后,中位数左侧的所有元素都小于中位数,而右侧的所有元素都大于中位数。但是如何在 O(n) 时间内找到距离中位数最近的 k 个邻居?
如果中位数为n,则左边数小于n,右边数大于n。 但是,数组未按左侧或右侧排序。这些数字是用户给出的任何一组不同的数字。
问题来自 Cormen 的 Introduction to Algorithms,问题 9.3-7
最佳答案
似乎没有人完全掌握这一点。这是如何做的。首先,如上所述找到中位数。这是 O(n)。现在将中位数放在数组的末尾,并从每个其他元素中减去中位数。现在找到数组的元素 k(不包括最后一个元素),再次使用快速选择算法。这不仅找到元素 k(按顺序),它还离开数组,以便最小的 k 数字位于数组的开头。一旦您重新添加中位数,这些就是最接近中位数的 k。
关于algorithm - 如何在 O(n) 时间内找到 n 个不同数字的中位数的 k 个最近邻居?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1557678/