求无序数组的中位数

这里先记录一下：

最近需要调试好的代码和学习的东西：

1 两个字符串的最大的相同字串

2 求单链表的倒数第K个元素

4 求无序数组的第K大的值

5 复习博客，看自动化测试框架

6 Mysql关系型和非关系的有什么区别

7 怎么优化查询？索引建立越多越好吗？如果内存足够呢，不考虑消耗空间？

8 B树插入删除说一下？

9 B树和B+树有什么区别？

求无序数组的中位数，我们首先想到的是将该数组进行排序，然后找到中间的元素，但是往往面试的时候，面试官就会怼你，说你时间复杂度太高了....要你优化（个人感觉，面试官对你问了问题，有一个自己的标准，如果你答不到他的点子上，他就不满意，各种怼，直到你想到他的标准，否则，挂掉），针对上面的问题，用一下两种方法求解

1 先排序后取中间值：

注意：python 3里面的运算符："//"：取整 "/" ：真除法 "~"：按位取反运算符：对数据的每个二进制位取反,即把1变为0,把0变为1 。~x类似于 -x-1

def get_middle(array):
    array.sort()
    index = len(array)//2
    return (array[index]+array[~index])/2

print(get_middle([2,1,5,8,3,9,4]))
print(get_middle([2,1,5,8,3,9,4,6]))

求无序数组的中位数

2 通过构建最小堆来求解

思想是：

1 对无序数组的前len(array)//2长度的元素建立最小堆，这样就得到了一个堆顶元素小于任意一个堆里的元素

2 将剩下的一半元素依次与堆顶元素比较。若比堆顶元素大，则替换之，并调整堆。（也就是说：依次遍历剩下一般的元素，与当前的堆顶元素作比较，如果大于堆顶元素，则替换，这时，重新调整堆的结构，使其保持为最小堆，否则，遍历下一个元素，知道剩下的一半元素遍历结束）

3 数组剩下的所有元素比较完后，可以输出中位数。数组长度为奇数时，输出堆顶元素即可。数组长度为偶数时，输出堆顶元素与它的孩子结点中较小的那个的均值。

def heap_adjust(parent,heap):   #更新结点后进行调整
    child=2*parent+1
    while len(heap)>child:
        if child+1<len(heap) and heap[child+1]<heap[child]:
            child+=1
        if heap[parent]<=heap[child]:
            break
        heap[parent],heap[child]=heap[child],heap[parent]
        parent,child=child,child*2+1
 
def find(nums):
    heapnum=len(nums)//2
    heap=nums[:heapnum+1]
    for i in range(len(heap)//2-1,-1,-1):   #前n/2个元素建堆
        heap_adjust(i,heap)
    for j in range(heapnum+1,len(nums)):
        if nums[j]>heap[0]:
            heap[0]=nums[j]
            heap_adjust(0,heap)
    #奇数时是最中间的数，偶数时是最中间两数的均值
    return heap[0] if len(nums)%2==1 else float(heap[0]+min(heap[1],heap[2]))/2

print(find([2,1,5,8,3,9,4,6]))
print(find([2,1,5,8,3,9,4]))

求无序数组的中位数

求无序数组的中位数

1 先排序后取中间值：

2 通过构建最小堆来求解

相关推荐