16

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

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

问题来自 Cormen 的算法介绍，问题 9.3-7

4

13 回答 13

20

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

于 2012-05-09T06:08:59.913 回答
10

中位数的中位数可能对找到最近的邻居没有多大帮助，至少对于较大的 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)。

于 2009-10-13T01:18:58.647 回答
4 
med=Select(A,1,n,n/2)   //finds the median

for i=1 to n
   B[i]=mod(A[i]-med)

q=Select(B,1,n,k) //get the kth smallest difference

j=0
for i=1 to n
   if B[i]<=q 
     C[j]=A[i] //A[i], the real value should be assigned instead of B[i] which is only the difference between A[i] and median.
       j++
return C
于 2010-09-08T13:59:30.807 回答
3

你可以这样解决你的问题：

您可以使用 O(n) nth_element 算法找到 O(n), wg 中的中位数。

您遍历所有元素，用一对替换每个元素：

the absolute difference to the median, element's value.

再一次用 n = k 做 nth_element。应用此算法后，您可以保证在新数组中首先具有绝对差的 k 个最小元素。你把他们的指数和完成！

于 2013-07-03T15:15:14.027 回答
2

四个步骤：

  1. 使用中位数的中位数来定位数组的中位数 - O(n)
  2. 确定中位数和数组中每个元素之间的绝对差并将它们存储在一个新数组中 - O(n)
  3. 使用Quickselect或Introselect从新数组中挑选出 k 个最小元素 - O(k*n)
  4. 通过索引原始数组来检索 k 个最近的邻居 - O(k)

当 k 足够小时，整体时间复杂度变为 O(n)。

于 2018-08-13T07:36:53.420 回答
1
  1. 求 O(n) 中的中位数。2. 创建一个新数组，每个元素是原始值的绝对值减去中位数 3. 在 O(n) 中找到第 k 个最小的数 4. 期望的值是与中位数的绝对差小于或等于新数组中第 k 个最小的数。
于 2019-05-04T20:31:44.827 回答
0

您已经知道如何在 O(n) 中找到中位数

如果顺序无关紧要，可以在 O(n) 中选择 k 最小值

来自维基百科

 function findFirstK(list, left, right, k)
 if right > left
     select pivotIndex between left and right
     pivotNewIndex := partition(list, left, right, pivotIndex)
     if pivotNewIndex > k  // new condition
         findFirstK(list, left, pivotNewIndex-1, k)
     if pivotNewIndex < k
         findFirstK(list, pivotNewIndex+1, right, k)

不要忘记 k==n 返回原始列表的特殊情况

于 2009-10-13T01:35:57.690 回答
0

您可以在 numbers 列表上使用非比较排序，例如基数排序，L然后通过考虑 k 个元素的窗口并检查窗口端点来找到 k 个最近邻居。另一种表述“找到窗口”的方式是找到最小化abs(L[(n-k)/2+i] - L[n/2]) + abs(L[(n+k)/2+i] - L[n/2])（如果 k 是奇数）或abs(L[(n-k)/2+i] - L[n/2]) + abs(L[(n+k)/2+i+1] - L[n/2])（如果 k 是偶数）的 i。结合案例，abs(L[(n-k)/2+i] - L[n/2]) + abs(L[(n+k)/2+i+!(k&1)] - L[n/2]). 找到最小值的一种简单的 O(k) 方法是从 i=0 开始，然后向左或向右滑动，但您应该能够在 O(log(k)) 中找到最小值。

您最小化的表达式来自转换L为另一个列表，M，通过获取每个元素与中位数的差异。

m=L[n/2]
M=abs(L-m)

i最小化M[n/2-k/2+i] + M[n/2+k/2+i]。

于 2009-10-13T01:40:49.007 回答
0

其实，答案很简单。我们需要做的就是选择与中位数绝对差最小的 k 个元素，当中位数在索引 m 处时，中位数从 m-1 移动到 0 和 m+1 到 n-1。我们使用与合并 2 个排序数组相同的想法来选择元素。

于 2009-10-14T03:51:22.493 回答
-1

如果您知道中位数的索引，可能只是 ceil(array.length/2)，那么它应该是列出 n(xk)、n(x-k+1)、...的过程, n(x), n(x+1), n(x+2), ... n(x+k) 其中 n 是数组，x 是中位数的索引，k 是邻居的数量你需要。（也许k / 2，如果你想要总k，而不是每边k）

于 2009-10-13T00:44:50.917 回答
-1

首先使用该复杂度的标准算法O(n)及时选择中位数。然后再次遍历列表，选择最接近中位数的元素（通过存储最知名的候选者并将新值与这些候选者进行比较，就像搜索最大元素一样）。

在此额外运行的每个步骤中，需要 O(k) 个步骤，并且由于 k 是恒定的，因此这是 O(1)。因此，额外运行所需的总时间为 O(n)，完整算法的总运行时间也是如此。

于 2009-10-13T00:52:20.017 回答
-1

由于所有元素都是不同的，因此最多可以有 2 个元素与平均值的差异相同。我认为拥有 2 个数组 A[k] 和 B[k] 表示与平均值之差的绝对值对我来说更容易。现在的任务是通过在 A[i+1] 和 B[i+1] 之前读取 A[i] 和 B[i] 的数组的前 k 个非空值来填充数组并选择 k 个元素。这可以在 O(n) 时间内完成。

于 2009-10-13T02:43:58.117 回答
-1

所有建议从数组中减去中位数的答案都会产生不正确的结果。此方法将查找值最接近的元素，而不是位置最接近的元素。

例如，如果数组是1,2,3,4,5,10,20,30,40. 对于 k=2，返回的值为 (3,4)；这是不正确的。正确的输出应该是 (4,10)，因为它们是最近的邻居。

找到结果的正确方法是使用选择算法来查找上限和下限元素。然后通过直接比较从列表中找到剩余的元素。

于 2020-02-05T23:16:11.327 回答