本文转载自微信公众号《三分钟学前端》，作者安姐。转载本文请联系三分钟学习前端公众号。中位数是有序列表中间的数字。如果列表长度是偶数，则中位数是中间两个数字的平均值。例如[2,3,4]的中位数是3[2,3]的中位数是(2+3)/2=2.5设计一个支持以下两种操作的数据结构：voidaddNum(intnum)-将数据流中的整数添加到数据结构中。doublefindMedian()-返回到目前为止所有元素的中值。示例：addNum(1)addNum(2)findMedian()->1.5addNum(3)findMedian()->2高级：如果数据流中的所有整数都在0到100范围内，您将如何优化您的算法？如果数据流中99%的整数都在0到100的范围内，你将如何优化你的算法？看到这个动态数组得到中位数的问题，不要太激动，这个很适合用堆，查的是堆的经典应用：中位数问题，详见前端进阶算法9：看完这篇文章，你再也不会害怕堆排序、TopK、中位数问题了。面试理解法：用堆解题。两个堆：大顶堆：用于访问前n/2个小元素，如果n为奇数，用于访问第一个Math.floor(n/2)+1个元素小顶堆：用于存储取后n/2个小元素，根据题目要求，中位数为：n为奇数：中位数为大顶堆堆顶元素n为偶数：中位数为大顶堆堆顶元素当数组是动态数组时，每当有元素插入数组时，如何调整堆？如果插入的元素大于大顶堆的顶部，则将元素插入小顶堆；如果小，它们被插入到大的顶堆中。当插入完成后，如果大顶堆和小顶堆的元素个数不满足我们的要求，我们需要不断的将大顶堆的堆顶元素或者小顶堆的堆顶元素移动到另一个堆中，直到满足要求代码实现：letMedianFinder=function(){//大顶堆，用于保存前n/2个小元素this.lowHeap=newMaxHeap()//小顶堆，用于savethenext/2Smallelementthis.hightHeap=newMinHeap()};//插入元素MedianFinder.prototype.addNum=function(num){//如果大顶堆为空或者大顶堆的堆顶元素小于num，则插入大顶堆//否则插入小顶堆if(!this.lowHeap.getSize()||num1){//从大堆迁移到小堆this.hightHeap.insert(this.lowHeap.removeHead())}if(this.hightHeap.getSize()>this.lowHeap.getSize()){//迁移小堆堆到大顶堆this.hightHeap.getHead())/2}returnthis.lowHeap.getHead()};其中小顶堆定义：//小顶堆letMinHeap=function(){letheap=[,]//堆中元素个数this.getSize=()=>heap.length-1//插入this.insert=(key)=>{heap.push(key)//获取存储位置leti=heap.length-1while(Math.floor(i/2)>0&&heap[i]{if(heap.length>1){if(heap.length===2)returnheap.pop()letnum=heap[1]heap[1]=heap.pop()heapify(1)returnnum}returnnull}//获取堆头this.getHead=()=>{returnheap.length>1?heap[1]:null}//heapify=(i)=>{letk=heap.length-1//top-downheapifywhile(true){letminIndex=iif(2*i<=k&&heap[2*i]{lettemp=arr[i]arr[i]=arr[j]arr[j]=temp}}大顶堆定义：//大顶堆letMaxHeap=function(){letheap=[,]//堆中元素个数this.getSize=()=>heap.length-1//Insert大顶堆this.insert=(key)=>{heap.push(key)//获取存储位置leti=heap.length-1while(Math.floor(i/2)>0&&heap[i]>heap[Math.floor(i/2)]){swap(heap,i,Math.floor(i/2));//交换i=Math.floor(i/2);}}//获取堆头this.getHead=()=>{returnheap.length>1?heap[1]:null}//删除堆头并返回this.removeHead=()=>{if(heap.length>1){if(heap.length===2)returnheap.pop()letnum=heap[1]heap[1]=heap.pop()heapify(1)returnnum}returnnull}//heapletheapify=(i)=>{letk=heap.length-1//自顶向下堆while(true){letmaxIndex=iif(2*i<=k&&heap[2*i]>heap[i]){maxIndex=2*i}if(2*i+1<=k&&heap[2*i+1]>heap[maxIndex]){maxIndex=2*i+1}if(maxIndex!==i){swap(heap,i,maxIndex)i=maxIndex}else{break}}}letswap=(arr,i,j)=>{lettemp=arr[i]arr[i]=arr[j]arr[j]=temp}}复杂度分析：时间复杂度：由于向堆中插入元素的时间复杂度为O(logn)，也就是树的高度；移动堆顶元素需要堆，时间复杂度也是O(logn)；因此，insert(addNum)findMedian的时间复杂度为O(logn)。每次插入后求中位数只需要返回堆顶元素即可。findMedian的时间复杂度是O(1)空间复杂度：O(n)如果所有的Integer都在0到100之间，我们可以尝试使用计数排序，但是计数排序的时间复杂度是O(n+m),其中m代表数据范围，复杂度高，这里不适合，计数排序更适合静态数组的topk最值问题leetcode347：topK个高频元素leetcode：https://leetcode-cn。com/问题s/find-median-from-data-stream/solution/javascriptshu-ju-liu-de-zhong-wei-shu-by-user7746o/
