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      

【解題思路】

最簡單的做法是直接把資料放到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時就讓數組有序，每次插入的時間複雜度為O(n)，再次運作仍然TOL

1 public static void addNum(int num) {
 2         
 3         int indexOfNumBiggerThanInput = 0;
 4         int i = 0;
 5         for (; i < nums.size(); i ++) {
 6             if (num < nums.get(i)) {
 7                 indexOfNumBiggerThanInput = i;
 8                 break;
 9             }
10         }
11         
12         if (indexOfNumBiggerThanInput != i) {
13             nums.add(i, num);
14         } else {
15             nums.add(indexOfNumBiggerThanInput, num);
16         }
17     }      

addNum如果一直有序采用二分插入會提高效率，時間複雜度O(lgn)

轉載于:https://www.cnblogs.com/feiling/p/5055542.html