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:
For example:
add(1) add(2) findMedian() -> 1.5 add(3) findMedian() -> 2
【解题思路】
最简单的做法是直接把数据放到ArrayList中，每次计算Median时先对ArrayList排序，然后计算Median
1 class MedianFinder { 2 3 private ArrayList<Integer> nums = new ArrayList<Integer>(); 4 5 // Adds a number into the data structure. 6 public void addNum(int num) { 7 nums.add(num); 8 } 9 10 // Returns the median of current data stream 11 public double findMedian() { 12 Collections.sort(nums); 13 14 int count = nums.size(); 15 16 if (count % 2 == 0) { 17 // even 18 int index2 = count / 2; 19 int index1 = index2 - 1; 20 21 return (nums.get(index1) + nums.get(index2)) / 2.0; 22 } else { 23 // odd 24 int index = count / 2; 25 26 return nums.get(index); 27 } 28 } 29 }
代码提交后，结果显示超时。
看了下超时测试用例，有2w多addNum操作，每个addNum操作后面紧跟着一个findMedian操作，每次findMedian需要对数组重新排序，事件复杂度为O(nlgn)
稍微优化点的做法是，在addNum时就让数组有序
leetcode -- Find Median from Data Stream
原文：http://www.cnblogs.com/feiling/p/5055542.html