查找未排序数组的中位数而不进行排序 [英] Find the median of an unsorted array without sorting

问题描述

有没有一种方法可以找到未排序数组的中位数: 1-不排序. 2-不使用选择算法，也不使用中位数的中位数

is there a way to find the Median of an unsorted array: 1- without sorting it. 2- without using the select algorithm, nor the median of medians

我发现了很多与我相似的其他问题.但是，大多数(即使不是全部)解决方案都讨论了SelectProblem和MedianOfMedians

I found a lot of other questions similar to mine. But the solutions, most of them, if not all of them, discussed the SelectProblem and the MedianOfMedians

推荐答案

您当然可以在不对数组进行排序的情况下找到它的中位数.有效地做到这一点并不容易.

You can certainly find the median of an array without sorting it. What is not easy is doing that efficiently.

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

For example, you could just iterate over the elements of the array; for each element, count the number of elements less than and equal to it, until you find a value with the correct count. That will be O(n²) time but only O(1) space.

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

Or you could use a min heap whose size is just over half the size of the array. (That is, if the array has 2k or 2k+1 elements, then the heap should have k+1 elements.) Build the heap using the first array elements, using the standard heap building algorithm (which is O(N)). Then, for each remaining element x, if x is greater than the heap's minimum, replace the min element with x and do a SiftUp operation (which is O(log N)). At the end, the median is either the heap's minimum element (if the original array's size was odd) or is the average of the two smallest elements in the heap. So that's a total of O(n log n) time, and O(n) space if you cannot rearrange array elements. (If you can rearrange array elements, you can do this in-place.)

这篇关于查找未排序数组的中位数而不进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！