295. 數據流的中位數

• 本題的第一個難點，要自己構造一個類（因為個人構造類的題目做的較少）
  屬性： 數組的長度int 數組的數據結構 List
• 保證原數組是一個有序數組，我使用了二分查找插入新元素。（類似于35.搜索插入位置）
  ① 當前數據結構沒有元素時，直接插入數據結構尾部
  ② 當要插入的元素大于數據結構中最后一個元素時，直接插入數據結構的尾部。
  ③ 其他的元素按照二分查找的方法插入數據結構中，List 的 add(position, num)方法。
• 沒學會大小堆。。。。先用我的垃圾方法得了

class MedianFinder {int size;List<Integer> lis;public MedianFinder() {size = 0;lis = new ArrayList<>();}// 要保持原數組的有序插入// 二分法查找插入public void addNum(int num) {int left = 0;int right = size-1;if(size == 0){lis.add(num);size++;return;}if( num > lis.get(right)){lis.add(num);size++;return;}  int middle = 0;while(left <= right){middle = left + (right - left)/2;if(lis.get(middle) > num){right = middle - 1;}else if(lis.get(middle) < num){left = middle + 1;}else{lis.add(middle, num);size++;return;}}lis.add(left, num);size++;// 用于打印測試// for(int tmp: lis){//     System.out.println(tmp);// }// System.out.println("*");}public double findMedian() {double median = 0.0;if(size % 2 == 1){median = lis.get(size/2);}else{median = (lis.get((size-1)/2)+lis.get(size/2))/2.0;}return median;}
}