题目
思路1：因为所有的数据都有可能在后来成为中位数，因此所有的数据都要保存，为了方便在中间插入数据，选用LinkedList来保存数字，（1）插入操作为：用二分查找定位待插入数所处的位置，然后插入数字，时间复杂度O(logN)；（2）选取中位数就是很简单的先判断总数是奇数还是偶数，然后取中间的数即可,时间复杂度O(1)。
关键点：用二分查找定位的时候如果找到数字则在这个数字前面插入即可，如果没找到数字，那么mid值一定在待插入数的前面或后面，只需要判断二者的大小关系然后插入即可。
易错点：（1）37行，mid的值可能是越界的，因此必须先判断（2）48行应该是（size-1）/2而不是size/2
感想：本来是很简单的一道题，但因为上述两个错误调试了半天，因此以后要特别注意数组越界问题。
思路1代码
思路2：把所有元素分成两部分，用一个最小堆保存较大的元素，用一个最大堆保存较小的元素，满足最小堆的元素一定大于等于最大堆的元素且二者的大小（size）之差不超过一，那么如果总size是奇数则返回size较大的元素的顶，否则返回两个堆顶的平均数，堆用priorityQueue表示。
易错点：(1)在insert方法中的条件判断，如果想插入到max，条件不应该是num>big.peek()而是num>small.peek(); (2)需要加入38,42行中size==0的判断，以免出现空指针错误
分析：
（1）下面代码中的判断有点繁琐，也可以采用另一种更简单的判断方式：以size为偶数为例，不管num的大小如何都先插入到small，再把small.poll()插入到big；
（2）对比方法1，二者的时间复杂度是相同的（因为PriorityQueue是通过堆来实现的，插入操作的复杂度也是O(logN)），但是方法二每次插入面对的数据集要小一半，因此可以认为比方法一少一次比较，但是如果出现需要调整的情况，即类似small.offer(big.poll())的情况，操作的代价是比较高的。
思路二代码
网友评论