如题所述
第1个回答 2022-06-04
中位数为一个排序数组的中间元素。假设对于一个排序数组A，数组长度为n，如果n为奇数，即中位数为A[(n-1)/2]；如果n为偶数，中位数则是(A[n/2]+A[n/2-1])/2。那么对于一个无序数组，应该如何寻找它的中位数？
一种很容易想到的方法就是对无序数组排序，然后可以直接得到该数组的中位数，时间复杂度为O(nlogn)。
我们可以使用快排思想快速找中位数，即先挑选一个数作为标准，以该元素为支点，将数组划分为两部分。这个问题可以抽象化为寻找第K大的数，快排每排完一轮之后左侧都是比他小的元素，右侧都是比他大的元素，那么支点的index（假设为N-1）即为第N大的数。当N == K，我们就找到了第K大的数；当N > K时， 第K大的数在[0,N-1]范围内；当N < K时，第K大的数在[N+1,n-1] (n为数组长度)范围内，利用递归即可找到第K大的数。
具体到寻找中位数，可分为两种情况：如果数组长度为奇数，即为寻找第(n+1//2)大的数；如果为偶数，则为分别寻找第(n//2+1)和第(n//2)大的数，然后求其平均值。具体程序如下：
我们可以构造一个最小堆，通过维护最小堆，即可得到无序数组的中位数。同样地，这个问题可以延伸至求数组的第K小的数。
一种很容易想到的方法就是对无序数组排序，然后可以直接得到该数组的中位数，时间复杂度为O(nlogn)。
我们可以使用快排思想快速找中位数，即先挑选一个数作为标准，以该元素为支点，将数组划分为两部分。这个问题可以抽象化为寻找第K大的数，快排每排完一轮之后左侧都是比他小的元素，右侧都是比他大的元素，那么支点的index（假设为N-1）即为第N大的数。当N == K，我们就找到了第K大的数；当N > K时， 第K大的数在[0,N-1]范围内；当N < K时，第K大的数在[N+1,n-1] (n为数组长度)范围内，利用递归即可找到第K大的数。
具体到寻找中位数，可分为两种情况：如果数组长度为奇数，即为寻找第(n+1//2)大的数；如果为偶数，则为分别寻找第(n//2+1)和第(n//2)大的数，然后求其平均值。具体程序如下：
我们可以构造一个最小堆，通过维护最小堆，即可得到无序数组的中位数。同样地，这个问题可以延伸至求数组的第K小的数。
