在未排序列表中查找近似中位数
我想在未排序列表中找到近似中位数，我知道两种算法
算法1-快速选择
算法 2 - 中位数的中位数
我不能在我的项目中使用快速选择，因为它在最坏的情况下需要O(n^2。我听说过中位数，但我的同事建议它需要O(n)和一些常数因子，因此它的时间复杂度是Cn，常数因子比quickselect大。我想知道与中位数相关的常数因子是什么？为什么中位数不使用9元素的伪中位数？< br >或者，他们是否有任何其他算法来寻找线性时间O(n)中的近似中值？
共有1个答案
虽然我不会很快放弃快速选择，因为使用正确选择的枢轴，它的最坏情况性能是非常不可能的......
也许是内向选择：
Introselect(内省选择的缩写)是一种选择算法，它是快速选择和中位数的混合，具有快速的平均性能和最佳的最坏情况性能。
内选择的工作原理是乐观地从快速选择开始，只有在递归次数过多而没有取得足够进展的情况下才切换到最差时间线性算法。切换策略是该算法的主要技术内容。简单地将递归限制在恒定深度是不够的，因为这会使算法在所有足够大的列表上切换。Musser讨论了几种简单的方法：
- 跟踪到目前为止处理的子分区的大小列表。如果在任何一点进行了k次递归调用而没有将列表大小减半，对于一些小的正k，请切换到最坏情况下的线性算法
- 求和到目前为止生成的所有分区的大小。如果超过列表大小乘以某个小的正常数k，则切换到最坏情况下的线性算法。这个总和很容易在单个标量变量中跟踪
这两种方法都将递归深度限制为k⌈对数n⌉ = O（logn）和到O（n）的总运行时间。
-
求一个未排序数组的中值，我们可以对n个元素做O(nlogn)时间的min-heap，然后我们可以逐个抽取n/2个元素得到中值。但是这种方法需要O(nlogn)时间。 我们能在O(n)时间内通过某种方法做同样的事情吗？如果可以，那么请告诉或建议一些方法。
-
问题内容： 我想知道是否有可能找到一个最接近的元素的元素 ，是不是 在那里。 例如，如果我们具有[1,3,6,7]值，并且正在寻找最接近4的元素，则它应返回3，因为3是数组中的最大数字，小于4。 我希望这是有道理的，因为英语不是我的母语。 问题答案： 如果数组已排序，则可以在以下位置进行修改的二进制搜索：
-
给定一个未排序的数组，我试图找到最接近数组中位数的 K 个元素。我在线性运行时间内找不到解决方案。 这里的中位数是6。 答案是2,3,4,5,6。 任何帮助或提示将不胜感激。
-
这是来自coursera的算法课程中的实践问题;我被困了几个星期。 问题在于：＜code＞给定一个由n个不同的未排序元素x＜sub＞1＜/sub＞组成的数组，x＜sub＞2＜/sub＞，…，x＜sub＞n＜/次级＞ε，加权中值是一个元素xk，对于该元素，值小于xk的所有元素的总权重最多为（总权重）/2，值大于xk的元素的总重量最多为（总重）/2。观察最多有两个加权值。演示如何在O（n）最坏时间内计
-
问题内容： 嘿。我有一个很大的数组，我想找到第N个最大值。我可以简单地对数组进行排序，然后采用第N个元素，但是我只对一个元素感兴趣，因此可能有比对整个数组进行排序更好的方法… 问题答案： 排序至少需要O（nlogn）运行时间- 有非常有效的选择算法可以在线性时间内解决您的问题。 （有时是），它基于quicksort（递归分区）的思想，是一个很好的解决方案（请参阅伪代码的链接+另一个示例）。
-
我试图找到给定排序数组的最大K数。 ex：输入- 到目前为止，我编写的代码返回最大的K元素，但它需要返回最大的K数字。任何帮助都将不胜感激。