arrays - 在不排序的情况下找到未排序数组的中位数

Question

<分区>

Answer 1

你当然可以在不排序的情况下找到数组的中位数。有效地做到这一点并不容易。

例如，您可以只遍历数组的元素；对于每个元素，计算小于和等于它的元素数，直到找到具有正确计数的值。这将是 O(n²) 时间，但只有 O(1) 空间。

或者您可以使用大小刚好超过数组大小一半的最小堆。 (也就是说，如果数组有 2k 或 2k+1 元素，那么堆应该有 k+1 元素。)构建堆使用第一个数组元素，使用标准堆构建算法(即 O(N))。然后，对于每个剩余元素 x，如果 x 大于堆的最小值，则将最小元素替换为 x 并执行 SiftUp 操作(这是 O(log N))。最后，中值要么是堆的最小元素(如果原始数组的大小是奇数)，要么是堆中两个最小元素的平均值。因此，如果不能重新排列数组元素，则总共需要 O(n log n) 时间和 O(n) 空间。 (如果您可以重新排列数组元素，则可以就地执行此操作。)