问题标签 [median-of-medians]

我在这里找到了 c++ 中的算法实现 https://gist.github.com/andlima/1774060 但我不明白几行的目的以及它们是如何工作的，

1. 我是否应该添加一个 if 语句，如果 n 低于一定数量，我们应该对数组进行排序并返回 v[k]？
2. 在第 4 行中，为什么我们通过将变量增加 4 来创建变量？我知道我们必须将它除以 5 才能拥有一定数量的小数组
3. 6行中的“for循环”负责什么？是否将主数组拆分为我们想要排序的较小数组，然后创建一个中位数数组？为什么有一个交换函数，为什么我们把它分成 if 和 else 条件？
4. 为什么我们在之前调用相同的函数行后删除中位数数组
5. 第 25 行中的 for 循环和第 33 行中的循环以及第 38 行中的交换的目的是什么？

对于这方面的任何帮助，我将不胜感激。

我读到快速选择的时间复杂度是：

我将上述内容读作“从 n 个元素中快速选择所需的时间 =（从 7n/10 个元素中选择所需的时间）+（从 n/5 个元素中快速选择所需的时间）+（一些 const *n）”

所以我知道一旦我们找到合适的枢轴，只剩下 7n/10 个元素，并且进行一轮安排枢轴需要时间 n。

但是 n/5 部分让我感到困惑。我知道这与中位数有关，但我不太明白。根据我的理解，中位数的中位数递归地分成 5 并找到中位数，直到你得到 1。

我发现这样做所花费的时间大约是 n 所以 T of mom(n)=n

你如何将 quick_select(n) = T_mom(n)/5 的 T 等同起来？

换句话说，这就是我认为等式应该写的：

有人可以告诉我哪里出错了吗？

我有一个大小为n的未排序数组，我需要找到k-1 个除数，因此每个子集的大小都相同（就像数组排序后一样）。

我用k-1=3看到了这个问题。我想我需要中位数的中位数，这将需要o(n)。但我认为我们应该这样做k次所以o(nk)。
我想了解为什么需要o(n logk)。

例如：我有一个未排序的整数数组，我想找到第k个除数，这是根据值将数组拆分为 k（相同大小）子数组的 k-1 个整数。
如果我有[1, 13, 6, 7, 81, 9, 10, 11]3=k 分隔符，则分割[7 ,11]到[1 6, 9 10 13 81]每个子集都大为 2 且相等的位置。

我打算用 C++ 实现这些算法，但遇到了一个问题。当我传递带有重复元素的数组并询问一些订单统计信息时会发生什么？当我从数组 [1,2,1] 询问二阶统计信息时，它应该返回 1 还是 2 ？如果 2，是否有任何快速的方法来编辑这些算法以使它们适应那种数组？将重复到数组末尾的元素移动是一种好方法吗？

两个排序的整数数组，A[1..N]并按升序B[1..N]提供。

问：设计一个O(log N)-time算法来找出所有 2N 个整数的中位数。N 可能不是 2 的幂。

为了简单起见，我们可以假设O(1)算法返回m如下：

我的问题：

1. N可能不是power of 2，是什么意思？（了解）
2. 我不知道如何更改输入并 在找到数组min和.maxAB

我已经给出了一个问题，即给定两个数组 A 和 B 按升序排序。我需要设计一个 clogn 时间算法来找到所有 2N 个整数的中位数。问题指出 N 可能不是 2 的幂。解决问题的提示是找到两个数组的最小值和最大值，然后更改输入并使长度为 2 的幂。

我当前的问题：由于两个数组已排序，因此两个数组的第一个元素将是最小值，最后一个元素将是最大值。那么在这里我如何更改输入并使长度为 2 的幂？

注意：这个问题是昨天深夜发布的，没有得到足够的答案。我添加了一些细节并重新发布。

作为一项任务，我的任务是创建中位数排序的中位数，这也可以确定数组的第 n 个最小元素（即排序数组的索引 0 是第一个最小的）。这种类型是递归的，这导致我无法理解它，因为我没有广泛使用递归。

通过拼凑教程和对算法的研究，我已经非常接近成功地创建该方法；但是，我目前返回了错误的值。当我希望它返回索引 0 处的值时，QS(A, 1) 的输入将返回索引 1 处包含的值：

为了将最终返回的索引修改为-1，我很难理解该算法中的递归。我不能简单地进行以下更改：

因为这有时会导致return QS(rightArray, k - left.size())传递的参数小于 1。我也不认为我可以添加：

由于算法的递归性质声明。我已经有一段时间没有成功，并且非常感谢任何关于我应该去哪里解决这个问题的迹象。

教科书 Intro to Algorithms (CLRS) 的问题 9-3描述了一种快速 O(n) 算法，用于查找长度为 n 的数组的第 k 阶统计量（排序时数组中的第 k 个元素），对于特定的k 远小于 n 的情况。当 n 为奇数时，我不确定该算法的正确性，并希望找到一种方法来证明它是正确的。

基本思想是我们首先将数组分成两半，第一部分包含 floor(n/2) 个元素，第二部分包含 ceil(n/2) 个元素。然后，我们将前半部分的每个元素与后半部分的相应元素“配对”。当 n 为奇数时，这会留下一个剩余的未配对元素。

对于每一对合作伙伴，我们确保左合作伙伴 >= 右合作伙伴，如果不是，则交换两者。然后，递归地找到下半场的 k 阶统计量，将下半场进行的任何交换与上半场的相应交换镜像。之后，整个数组的k阶统计量要么在前半部分的前k个元素中，要么在后半部分的前k个元素中。

我的困惑来自数组长度 n 为奇数的情况，并且后半部分有一个单独的元素没有伙伴。由于递归是在后半部分执行的，由数组的最后一个 ceil(n/2) 元素组成，包括唯一的无伙伴最后一个元素，我们应该将下半部分进行的所有交换与相应的交换中的交换进行镜像上半场的合作伙伴，当其中一个交换涉及到最后的元素时，不清楚该怎么做，因为它没有合作伙伴。

教科书似乎没有特别注意这个问题，所以我假设当交换涉及到最后一个元素时，那么上半场就不要做任何镜像动作。结果，最后一个元素只是简单地“窃取”了与之交换的任何人的伙伴。但是，在这种情况下，是否有一种简单的方法可以查看算法是否仍然正确？如果当最后一个元素窃取了别人的伙伴时，伙伴实际上是第 k 阶统计量，然后被交换到一个无法访问的位置怎么办？涉及顺序统计选择的递归和分区机制对我来说足够不透明，因此我不能自信地排除这种情况。

在命令提示符处查找给定 500GB 文件中所有数字的中位数。

文件格式例如：

每行有一个数字（数字可以重复）。任何人都可以帮忙解决如何在 JAVA 中处理这个问题吗？如果我们必须拆分文件，那么如何计算中位数？我在中位数上遇到过几篇帖子，但在如此巨大的文件上找不到最佳方法。

关于中位数的算法，我有一些不明白的地方。关于这个算法的一个关键步骤是找到一个近似的中位数，根据维基百科，我们保证这个近似中值大于初始集合元素的 30%。

为了找到这个近似的中值，我们计算每组 5 个元素的中值，我们将这些中值收集到一个新集合中，然后重新计算中值，直到获得的集合包含至少 5 个元素。在这种情况下，我们得到集合的中位数。（如果我的解释不清楚，请参阅维基百科页面）

但是，请考虑以下 125 个元素的集合：

因此，我们将集合划分为 5 个元素的组，计算并收集中位数，因此，我们得到以下集合：

我们重做相同的算法，我们得到以下集合：

所以我们得到近似的中位数是 27。但是这个数字大于或等于只有 27 个元素。并且 27/125 = 21.6% < 30%！！

所以我的问题是：我错在哪里？为什么在我的情况下，近似中位数不大于元素的 30%？？？？

谢谢您的回复！！