数据流中的中位数确实是轻敌了。转载本文请联系bigsai公众号。前言大家好，我是bigsai，今天好忙（后面就不透露了），给大家分享一道聪明的题，五分钟就能掌握。今天在刷题的时候遇到了一道hard题，也很有意思。我指着offer和Li按钮的第41个问题[数据流中的中位数]。题目描述是这样的：中位数是一个有序列表中间的数。如果列表长度是偶数，则中位数是中间两个数字的平均值。例如[2,3,4]的中位数是3[2,3]的中位数是(2+3)/2=2.5设计一个支持以下两种操作的数据结构：voidaddNum(intnum)-将数据流中的整数添加到数据结构中。doublefindMedian()-返回到目前为止所有元素的中值。其实问题也很简单，就是一组数据，求它的中位数，不同的是这组数据可能会加入一些其他的数据，也就是我们需要维护这样一个数据结构是尽可能高效地完成它。我点开这个问题电源键上的描述，好像在诱惑我，告诉我什么！然后以为真正的数据就在这个范围内，然后操作猛如虎，提交直接GG。不过这个问题是个很好的问题，以后再说吧，先仔细看看吧！好了，进入正题，看看如何分析这道经典题。小白级别的方法（无脑排序）老少皆宜解决这个问题。小白也有小白的方法。题目不难，只要你能过就可以了（只对小白有效）。一组数据存储，我可以用数组或者List，中位数其实就是中间那个（一个偶数的两次平均）数，也好办，排序！一个ArrayList()可以容纳百川（变长数组可以存储数据），一行Arrays.sort()走遍天下。它可以使用编程语言中的现有集合和API轻松实现！分析该算法的时间复杂度。每次插入都需要按nlogn排序，查询时间接近O(1)；如果多次的话，时间复杂度还是挺高的。具体代码为：/**initializeyourdatastructurehere.*/publicMedianFinder(){}Listlist=newArrayList<>();publicvoidaddNum(intnum){list.add(num);list.sort(null);}publicdoublefindMedian(){if(list.size()%2==1)returnlist.get(list.size()/2);else{return(double)(list.get((list.size()-1)/2)+list.get(list.size()/2))/2;}}看结果，2000+ms，这也是极限，这个方法仅限于小白，只为求成功。大白级方法（插入排序）大白比小白稍微强一点，年龄大一点，知道的多一点。大白一看：这个序列一开始是不存在的！然后在原来的基础上一点一点的增加长度。如果每次都把排序搞乱，成本有点高！那么能否复用上一次排序的结果呢？这不就是插入排序吗！每一个新的元素就相当于最后一步插入排序让它有序，然后插入...这个过程每次插入分为两部分，查找和移动，查找成本为O(n)，插入为也是O(n)。时间复杂度还是O(n)。可以维护一个常数来表示数据的总数。找中位数的时候，直接按照个数查找即可，时间复杂度为O(1)。与O(nlogn)相比，此时间复杂度在插入时优化为O(n)。很大的进步。不过聪明的大白也能找到一些亮点。数组的前面是有序的，但是在有序的序列结构中需要锁定最后插入的元素的位置。一个一个线性搜索太费时间了！这显然是一个二进制应用程序。场景！可以用二分法找到插入位置，然后插入。二进制+插入的时间复杂度是多少？记住，不是O(logn)，每次二分查找的时间复杂度确实是O(logn)，但是插入操作的时间复杂度还是O(n)，总的时间复杂度取最高级的O(logn)+O(n)=O(n)。那么如果以后在这里遇到面试官问你：使用二分查找优化的插入排序的时间复杂度是多少？你必须坚定地回答：是O(n2)，从字操作的角度来看，虽然查询变成了O(logn)但是插入仍然是O(n)，所以n个数的时间复杂度仍然是O(n2).好了，既然解释清楚了，操作起来猛如虎，直接上传代码：classMedianFinder{/**initializeyourdatastructurehere.*/publicMedianFinder(){}intarr[]=newint[50000];intcount=0;publicvoidaddNum(intnum){intlow=0,high=count-1;while(low<=high){intmid=(low+high)/2;intmidVal=arr[mid];if(midValnum)high=mid-1;elselow++;}for(inti=count-1;i>=low;i--){arr[i+1]=arr[i];}arr[low]=num;count++;}publicdoublefindMedian(){if(count%2==1)returnarr[count/2];elsereturn(double)(arr[count/2-1]+arr[count/2])/2;}}提交后，200+ms，比起小白的无脑排序，优化了很多，但也只打败了10%的用户，可见方法还是不够好，还是很白。老大的解决办法（双堆/优先队列）其实也能想出来，不过确实除了这个问题，我还没见过两支队伍这么玩，也算是开眼界了。前面讲了堆排序和优先级队列的原理，详细讲解了堆的数据结构。我们简单回顾一下堆：堆是一棵完全二叉树（即最后一层从左到右有连续的节点），因为是完全二叉树，所以我们经常用数组来存储，可以交换通过二叉树下标转换到一个好的锁定位置。堆分为大根堆和小根堆：如果所有节点都大于子节点值，则称这个堆为大根堆，堆的最大值在根节点。如果所有节点都小于子节点值，则称这个堆为小根堆，该堆的最小值在根节点处。了解这些基础知识就足以解决这个问题。heap和priorityqueue的具体实现这里就不用知道了。但是如何将堆和优先队列应用到这个中值搜索中呢？这非常巧妙。我们把数据分成两个堆，一个是小根堆，一个是大根堆。小根堆的存储容量最大。一半的数据，大的最小的在堆顶；大根存放最小的一半数据，小的最大的在堆顶，中位数只能在两个堆顶产生！但是在具体的实现过程中也有很多需要注意的地方。加的时候首先要判断其中一个顶堆的大小，应该加哪个堆（优先队列），但是加之后，值可能总是大大增加，也可能总是值减少。可能会造成两个堆的元素个数不平衡，所以必须把少的加到多的。这里我在实现时约束小根堆的元素个数等于大根堆的个数（偶数）或者等于大根堆的个数加一（奇数）。奇数的情况下，取小根堆顶返回即可。因为Java已经实现了优先级队列，所以不需要详细实现（可以参考我之前写的优先级队列实现）。分析这个时间复杂度，每次堆插入和删除的时间复杂度级别是O(logn/2)。即使在元素平衡面前多了两次操作，时间复杂度依然是O(logn)级别。比O(n)快很多，数据量越大越明显。具体代码为：classMedianFinder{/**initializeyourdatastructurehere.*/publicMedianFinder(){}Queueq1=newPriorityQueue<>();//小根堆的放大数据//大根堆Queueq2=newPriorityQueue<>(newComparator(){@Overridepublicintcompare(Integero1,Integero2){returno2-o1;}});publicvoidaddNum(intnum){if(q1.isEmpty())q1.add(num);elseif(num>q1.peek()){//插入到小根堆中q1.add(num);if(q1.size()>q2.size()+1){q2.add(q1.poll());}}else{//插入大根堆q2.add(num);if(q2.size()>q1.size()){q1.add(q2.poll());}}}publicdoublefindMedian(){if(q1.size()==q2.size())return(double)(q1.peek()+q2.peek())/2;elsereturnq1.peek();}}执行间隔是75ms，比上一个好太多了，这个doublestack真是妙啊！这也是我第一次看到它。Improvement对于这个问题，还是有一些牛鬼蛇神用二叉搜索树来做，理论上是可行的，但是插入效率不一定很稳定，查询效率比较低（二叉树的中序排序）.不过文章开头提到的场景问题还是需要慎重考虑的。面试场景很可能会问：1.如果数据流中的所有整数都在0到100的范围内，你会如何优化你的算法？2.如果数据流中99%的整数都在0到100的范围内，你如何优化你的算法？对于第一个问题，应该用什么方法来优化？如果还是用传统的双堆，如果数据量非常大的话，在效率上肯定还有优化的空间。当数据集中分布时，必须考虑计数和排序！如果数据分布在0-100之间，可以直接开一个大小为101的数组，遇到数字就在对应的位置值上加一，不仅0-100可以这样，但是也可以通过在一定范围内移动来表示。然后你求中位数，你只需要枚举叠加就可以找到中间的那个数。但是可以再优化一下，修改这个计数排序，用数组值来表示小于当前位置值的数。这样数组的值是不断增加的，搜索的时候也可以使用二分优化。但是，在具体实现方面，可能有一些事情需要你考虑。分析算法的复杂度。对于每一次插入操作，对应的下标和后面的值都要加1，所以操作次数不超过50次，查询操作使用二分法。10次??以上，所以数据对比集中的数据很多，重复的也很多。用计数排序就很好了。另外，如果99%在0-100范围内，也很容易，就是在前后边分别设置0和102，大于100的放102，小于0的放0，每次都把x放到x中。+1位置，因为中位数肯定在0-100之间，所以这仍然有效！
