4

我有一个包含 n 个成对不同元素的数组和一个 1<=k<=n 的数字 k。

现在我正在寻找一种算法来计算与k数字数组的中位数绝对差最小的数字。我需要线性复杂度（O(n)）。

我的做法：

我找到中位数：

  • 我对数字进行排序
  • 我得到中间元素，或者如果元素的数量甚至是中间和圆形中两个元素的平均值。

在那之后：

  • 我取每个数字并找到与中位数的绝对距离。这些结果我保存在不同的数组中
  • 我对新获得的数组进行排序。
  • 我取结果数组的前 k 个元素，我就完成了。

我不知道我的解决方案是否在O(n)，也不知道我是否对这个想法正确。有人可以验证吗？有人可以告诉我如何在 O(n) 中解决它吗？

4

1 回答 1

9

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

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

您遍历所有元素，用一对替换每个元素：<the absolute difference to the median>, <element's value>。n你再一次用=做 nth_element k。应用此算法后，您可以保证k在新数组中首先具有绝对差的最小元素。你把他们的指数和完成！

另一方面，您的算法使用排序，这使得它O(nlogn)。

编辑：请求的示例：

设数组为[14, 6, 7, 8, 10, 13, 21, 16, 23]。

  • 在找到中位数的步骤之后，它将被重新排序为：[8, 7, 9, 10, 13, 16, 23, 14, 21]，请注意数组未排序，但中位数 (13) 仍然正好在中间。
  • 现在让我们做一下让你感到困惑的对替换：我们创建一个新的对数组：[<abs(14-13), 14>, <abs(6-13), 6>, <abs(7-13), 7>, <abs(8-13), 8>, <abs(10-13), 10>, <abs(13-13), 13>, <abs(21-13), 21>, <abs(16-13), 16>, <abs(23-13), 23>。这样我们就得到了数组：[<1, 14>, <7, 6>, <6, 7>, <5, 8>, <3, 10>, <0, 13>, <8, 21>, <3, 16>, <10, 23>
  • 如果 egk是 4，我们再做一次 nth_element（使用每对的第一个元素进行比较）并获得：[<1, 14>, <3, 16>, <0, 13>, <3, 10>, <8, 21>, <7, 6>, <10, 23>, <6, 7>, <5, 8>]所以您搜索的数字是前 4 对的第二个元素：14、16和1310
于 2013-01-13T11:24:02.077 回答