LeetCode 剑指 Offer 41. 数据流中的中位数—— JavaScript

题链接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/

题描述：

解题思路：

利用数组存储数据并排序。

addNum()：
（1）找出添加的数据在数组中合适的位置
（2）插入该数据
findMedian()：
（1）如果数组长度为奇数，中位数等于数组中间的元素
（2）如果为偶数，则为中间两个数的平均值

代码实现：

var MedianFinder = function() {
    this.arr = [];
};
MedianFinder.prototype.addNum = function(num) {
    let index = -1;
    for (let i = 0; i < this.arr.length; i++) {
     if (this.arr[i] > num) {
      index = i;
      break;
     }
    }
    if (index != -1) {
     for (let i = this.arr.length; i > index; i--) {
      this.arr[i] = this.arr[i - 1];
     }
     this.arr[index] = num;
    } else {
     this.arr[this.arr.length] = num;
    }
   };
 MedianFinder.prototype.findMedian = function() {
    if (this.arr.length % 2 == 0) {
     return (this.arr[this.arr.length / 2] + this.arr[this.arr.length / 2 - 1]) / 2
    } else {
     return this.arr[Math.floor(this.arr.length / 2)];
    }
   };

时间复杂度：O(n)
空间复杂度：O(n)