理解“中位数的中位数”算法
我希望你能够理解“中位数的中位数”算法，以下是一个例子： 我们有45个不同的数字，分成9组，每组有5个元素。 48 43 38 33 28 23 18 13 8 49 44 39 34 29 24 19 14 9 50 45 40 35 30 25 20 15 10 51 46 4...
为什么中位数算法被描述为使用O（1）辅助空间？
维基百科将中位数算法列为需要O(1)辅助空间。 然而，在算法的中间，我们对一个大小为n/5的子数组进行递归调用以查找中位数。当递归调用返回后，我们使用返回的中位数作为枢轴来分割数组。 这个算法是否会因为递归而将O(lg n)激活记录推入运行时堆栈？据我所见，这些递归调用以查找连续的中位数似...
中位数算法的解释
Median of medians方法在quicksort类型的分区算法中非常流行，可以产生一个相当不错的基准点，使得它可以将数组均匀地划分。其逻辑在维基百科中给出如下所示： 选择的基准点对于中位数列表中约n/10个元素（每半部分为1/2 * (n/5)）都小于和大于一半的元素。其中每个...
寻找N^2个数字的中位数，但只有足够存储N个数字的内存。
我试图学习分布式计算，并遇到了一个在大型数据集中查找中位数的问题： 假设我们有一个大型的数字集合（假设元素数量为N*K），无法放入内存（尺寸为N）。我们如何找出这些数据的中位数？假设在内存中执行的操作是独立的，即我们可以考虑有K台机器，每台机器最多可以处理N个元素。 我认为可以使用...
不理解中位数法找到第k个元素的算法
以下是我尝试理解中位数算法（使用大小为5的块）的代码。我知道如何获取输入的中位数，但不确定如何编写块以递归输入，直到只有中位数为止。然后在获得该中位数之后，我不确定如何将其用作枢轴来丢弃无用信息以对输入进行分区。getMediansArray返回一个大小为ceil(input.length/5...