2

通过谷歌搜索几分钟，我知道了基本概念。

  1. 设 A、B 和 C 是包含 n 个元素的排序数组。
  2. 在每个数组中选择中值，并将它们称为 medA、medB 和 medC。
  3. 不失一般性，假设 medA > medB > medC。
  4. 数组 A 中大于 medA 的元素不能成为三个数组的中位数。同样，数组 C 中小于 medC 的元素不能，因此这些元素将被忽略。
  5. 递归地重复步骤 2-4。

我的问题是，基本情况是什么？假设有很多基本情况，我手动测试了几个小时的算法，但我找不到正确的基本情况。此外，三个数组的长度在每个递归步骤中都会变得不同。即使三个数组的长度不同，第 4 步是否有效？

4

2 回答 2

1

该算法适用于两个大小相同但不是三个的排序数组。一次迭代后，您消除了 A 和 C 中的一半元素，但 B 保持不变，因此这些数组中的元素数量不再相同，该方法不再适用。对于不同大小的数组，如果应用相同的方法，则会从下半部分和上半部分删除不同数量的元素，因此剩余元素的中位数与原始数组的中位数不同。

话虽如此，您可以修改算法以在每次迭代中消除两端相同数量的元素，当一些数组非常小而一些数组非常大时，这可能是有效的。您也可以将其变成寻找第 k 个元素的问题，跟踪被丢弃的元素数量并在每次迭代时更改 k 的值。无论哪种方式，这都比两个数组的情况要复杂得多。

还有一篇关于一般情况的帖子：Median of 5 sorted arrays

于 2013-09-16T21:40:41.787 回答
0

我认为您可以使用选择算法，稍作修改以处理更多数组。

您正在寻找中位数，即第p =[n/2]个元素。

选择最大数组的中位数，在其他两个数组中找到该值的分割点（二分查找，log(n)）。现在您知道所选数字是第k个（k = 位置的总和）。

如果 k > p，则丢弃其上方的 3 个数组中的元素，如果较小，则丢弃其下方的元素（可以通过分别为每个数组维护上下索引来实现丢弃）。如果它更小，也更新 p = p - k。

重复直到 k=p。

糟糕，我认为这是 log(n)^2，让我考虑一下...

于 2013-09-16T22:34:35.907 回答