从未排序数组的中位数中查找 K 个最接近的元素
给定一个未排序的数组，我试图找到最接近数组中位数的 K 个元素。我在线性运行时间内找不到解决方案。
A[] = 1, 2, 3, 4, 5 ,6 , 30 ,31, 32 ,33 ,34 # assume sorting part is done
这里的中位数是6。
答案是2,3,4,5,6。
任何帮助或提示将不胜感激。
共有1个答案
我的建议是分两步走。
首先，使用中值算法在线性时间内找到未排序阵列的中值。
其次，扫描数组并填充一个最大堆（大小为k），其中元素根据到中值的距离进行组织，以找到k个最近的元素。
通过以下方式确保堆包含的元素永远不会超过 k 个。当您想要将第 （k 1） 个元素添加到堆中时，请检查它是否小于根。如果是这样，则将其添加到堆中，并在重组堆后删除（新）根。如果没有，你可以丢弃它。
以上应该具有O（N log（k））的运行时间，其在N中是线性的。
-
我试图找到给定排序数组的最大K数。 ex：输入- 到目前为止，我编写的代码返回最大的K元素，但它需要返回最大的K数字。任何帮助都将不胜感激。
-
本文向大家介绍在C ++中从给定的三个排序数组中查找三个最接近的元素，包括了在C ++中从给定的三个排序数组中查找三个最接近的元素的使用技巧和注意事项，需要的朋友参考一下 假设我们有三个排序的数组A，B和C，以及分别来自A，B和C的三个元素i，j和k，使得max（| A [i] – B [i] |，| B [j] – C [k] |，| C [k] – A [i] |）被最小化。因此，如果A =
-
求一个未排序数组的中值，我们可以对n个元素做O(nlogn)时间的min-heap，然后我们可以逐个抽取n/2个元素得到中值。但是这种方法需要O(nlogn)时间。 我们能在O(n)时间内通过某种方法做同样的事情吗？如果可以，那么请告诉或建议一些方法。
-
本文向大家介绍Java程序从两个排序的数组中查找最接近的一对，包括了Java程序从两个排序的数组中查找最接近的一对的使用技巧和注意事项，需要的朋友参考一下 为了从两个排序的数组中找到最接近的一对，Java代码如下： 示例 输出结果 一个名为Demo的类包含一个名为closest_pair的函数，该函数遍历两个数组并检查哪个和与前面指定的数字非常接近。数组中的这对将作为输出返回。在main函数中，定
-
我遇到了以下leetcode问题，我对一些人用来解决它的方法有一个问题。问题是：给定一个非空二叉查找树和一个目标值，在BST中找到最接近目标的k个值。 注意：给定的目标值是浮点。 您可以假设k始终有效，即：k≤总节点。 保证BST中只有一组最接近目标的唯一k值。 所以，有些人所做的是，他们在保持k大小的最近元素队列的同时，按顺序遍历。在顺序遍历过程中，如果发现某个元素比队列中的第一个节点更接近目标
-
问题内容： 给定两个排序的整数数组和，以及一个整数，我必须找到这样的数组： 并尽可能大。 我能想到的最佳解决方案是 O （ n log n ）时间，从第一个数组中取出每个整数，然后找到“ ” 的下限。 有人可以建议我做一个更好的方法（也许是在O（ n ）时间）吗？ 问题答案： 想一想，然后您可能会问自己： “是否有必要每次都在排序的b数组中搜索a []的连续值？”