295. Find Median from Data Stream
实作一个资料结构,需实现两种操作:
1.addNum(int n)
把一个资料加入流
2.findMedian()
从资料流里面取出一个数字,若:
* 资料有偶数个:返回大小最接近中间的两数字,并相加除二
* 资料有奇数个:返回大小排序后刚好在正中间的数字
思路:
1.插入一个元素到List并排序他,直接排序整个List不意外吃了TLE,改用binary
search来找插入元素的位置,这样时间复杂度从O(nlogn)变成O(n),勉勉强强AC了。
(如果不存在数字,binarySearch返回的是负数的该元素应插入位置)
2.判断list的size来决定是要返回中间元素还是左右相加除二。
Java Code: