arrays - 在未排序的数组中查找中位数(仅限于使用在线性中查找季度元素的子例程)

Question

就像未排序数组的任何其他中值选择问题一样，但有额外的限制。我们需要使用提供的子例程/辅助函数 Quart(A,p,r)，它在线性时间内找到给定子数组中的第 1/4 个有序项。我们如何使用这个辅助函数来查找数组的中位数？

进一步限制:1. 您的解决方案必须就地执行(没有新的可以创建数组)。特别是，一种替代解决方案是将数组扩展到大小 m 以便 A[n+1, ... ,m] = 中的所有条目1 且 m > 2n。在此之后，您将能够解决中位数原始数组中的问题，只需调用一次四分位数问题在扩展数组中。有了进一步的限制，这是不可能的。2. 在运行算法时，您可以临时更改数组中的元素，例如，SWAP 更改元素。但是，在你的算法结束后，数组中的所有元素必须与开始时相同(但就像类里面教授的随机选择算法一样，它们的顺序可能与最初的顺序不同)。

由于不允许创建新数组，这意味着您只能修改少量(恒定)的项目。

Answer 1

• 遍历数组并找到最小值和最大值。
• 调用 Quart 求出四分位数值
• 遍历数组并将 (max - min) + 1 添加到四分位数以下的所有值。这会将值的底部四分之一移动到顶部
• 再次调用 Quart 以找到新值的四分位数(这将是原始值的中位数)
• 遍历数组并从所有大于最大值的值中减去 (max - min) + 1 以将数组返回到其原始状态

您可能需要一些额外的规则来处理特殊情况，例如如果有多个值等于四分位数。