《leetcode》：Find Median from Data Stream

本文主要是介绍《leetcode》：Find Median from Data Stream，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.
For example:

add(1)
add(2)
findMedian() -> 1.5
add(3) 
findMedian() -> 2

思路一：超时

借用一个List来保存数据，而findMedian函数的实现是先对List进行排序，然后进行取中间值。由于没取一次中间值就要排一次序，因此，报超时也是正常的。

实现代码如下：

    public class MedianFinder {private List<Integer> list = new ArrayList<Integer>();// Adds a number into the data structure.public void addNum(int num) {list.add(num);}// Returns the median of current data streampublic double findMedian() {Collections.sort(list);int len = list.size();return (len&0x01)==1?list.get(len/2):(list.get(len/2)+list.get(len/2-1))*1.0/2;}}

思路二

还是借用一个List来保存数据，只是保存数据的时候是按照升序来保存的，即在保存数据的时候，先找到其在List中要插入的位置，然后保存进行就保证了List永远是排序的。

这样，在调用findMedian时，就直接取出List中的中间的值即可。

    public class MedianFinder {private List<Integer> list = new ArrayList<Integer>();// Adds a number into the data structure.public void addNum(int num) {int len = list.size();//先处理三种特殊情况if(len==0){list.add(num);return ;}if(num>=list.get(len-1)){list.add(num);return;}if(num<list.get(0)){list.add(0, num);return ;}//利用二分查找找到num要插入的位置int left = 0;int right = len-1;int mid = -1;while(left<=right){mid = left + (right-left)/2;int val = list.get(mid);if(val==num){left = mid;break;}else if(val<num){//找到第一个大于num的数left = mid+1;}else if(val>num){right = mid-1;}}//left指向就是要插入的位置list.add(left, num);}// Returns the median of current data streampublic double findMedian() {//Collections.sort(list);int len = list.size();return (len&0x01)==1?list.get(len/2):(list.get(len/2)+list.get(len/2-1))*1.0/2;}};// Your MedianFinder object will be instantiated and called as such:// MedianFinder mf = new MedianFinder();// mf.addNum(1);// mf.findMedian();