就像未排序数组的任何其他中值选择问题一样，但有额外的限制。我们需要使用提供的子例程/辅助函数 Quart(A,p,r)，它在线性时间内找到给定子数组中的第 1/4 个有序项。我们如何使用这个辅助函数来查找数组的中位数？
进一步限制: 1. 您的解决方案必须就地执行(没有新的 可以创建数组)。特别是，一种替代解决方案是 将数组扩展到大小 m 以便 A[n+1, ... ,m] = 中的所有条目 1 且 m > 2n。在此之后，您将能够解决中位数 原始数组中的问题，只需调用一次四分位数问题 在扩展数组中。有了进一步的限制，这是不可能的。 2. 在运行算法时，您可以临时更改数组中的元素，例如，SWAP 更改元素。但是，在你的算法结束后，数组中的所有元素必须与开始时相同(但就像类里面教授的随机选择算法一样，它们的顺序可能与最初的顺序不同)。
由于不允许创建新数组，这意味着您只能修改少量(恒定)的项目。
最佳答案
- 遍历数组并找到最小值和最大值。
- 调用 Quart 求出四分位数值
- 遍历数组并将 (max - min) + 1 添加到四分位数以下的所有值。这会将值的底部四分之一移动到顶部
- 再次调用 Quart 以找到新值的四分位数(这将是原始值的中位数)
- 遍历数组并从所有大于最大值的值中减去 (max - min) + 1 以将数组返回到其原始状态
您可能需要一些额外的规则来处理特殊情况，例如如果有多个值等于四分位数。
关于arrays - 在未排序的数组中查找中位数(仅限于使用在线性中查找季度元素的子例程)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55146374/