解法 1:暴力法

每次取出中位数的时候，都先将所有元素进行排序，然后再计算中位数。代码如下：

复制
1
2var MedianFinder = function() {
3    this.data = [];
4};
5
6MedianFinder.prototype.addNum = function(num) {
7    this.data.push(num);
8};
9
10MedianFinder.prototype.findMedian = function() {
11    const length = this.data.length;
12    if (!length) {
13        return null;
14    }
15    this.data.sort((a, b) => a - b);
16
17    const mid = Math.floor((length - 1) / 2);
18    if (length % 2) {
19        return this.data[mid];
20    }
21    return (this.data[mid] + this.data[mid + 1]) / 2;
22};

也可以在添加元素的时候直接排序。时间复杂度一样，均是 O(NlogN)，无法 ac。

解法 2: 二分查找

其实不需要每次添加元素的时候，都对全部元素重新排序。如果之前一直保证元素是有序的，那么添加新元素的时候，只需要将元素插入到正确位置即可，查找正确位置可以通过「二分搜索」来完成。

为了保证之前的元素有序，针对每个新添加的元素都将其放入正确位置。

代码实现如下：

复制
1
2var MedianFinder = function() {
3    this.data = [];
4};
5
6MedianFinder.prototype.addNum = function(num) {
7    if (!this.data.length) {
8        this.data.push(num);
9        return;
10    }
11
12    let left = 0,
13        right = this.data.length - 1;
14    while (left <= right) {
15        let mid = Math.floor((left + right) / 2);
16        if (this.data[mid] === num) {
17            this.data.splice(mid, 0, num);
18            return;
19        } else if (this.data[mid] < num) {
20            left = mid + 1;
21        } else {
22            right = mid - 1;
23        }
24    }
25    this.data.splice(right + 1, 0, num);
26};
27
28MedianFinder.prototype.findMedian = function() {
29    const length = this.data.length;
30    if (!length) {
31        return null;
32    }
33
34    const mid = Math.floor((length - 1) / 2);
35    if (length % 2) {
36        return this.data[mid];
37    }
38    return (this.data[mid] + this.data[mid + 1]) / 2;
39};

二分查找需要O(logN)的复杂度，移动元素需要O(N)复杂度，所以时间复杂度是O(N)。

解法 3: 最大堆 + 最小堆

对于这种动态数据，堆是极好的解决方案。准备两个堆：

• 最大堆：存放数据流中较小的一半元素
• 最小堆：存放数据流中较大的一半元素

需要保证这 2 个堆的“平衡”。这里的平衡指得是：最大堆的大小 = 最小堆的大小， 或者 最大堆的大小 = 最小堆的大小 + 1。

当调用 findMedian 查询中位数的时候，中位数就是最大堆的堆顶元素，或者 (最大堆的堆顶元素 + 最小堆的堆顶元素)/2

剩下的问题就是怎么保证堆的平衡？步骤如下：

• 先让 num 入 maxHeap
• 取出 maxHeap 的堆顶元素，放入 minHeap
• 若此时最大堆的大小 < 最小堆的大小，取出 minHeap 的堆顶元素，让入 maxHeap

由于 JavaScript 中没有堆，所以要自己实现。在实现的时候，堆的代码其实只需要一份，堆中进行判定的比较函数由外界传入即可。

复制
1
2const defaultCmp = (x, y) => x > y; // 默认是最大堆
3
4const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
5
6class Heap {
7    /**
8     * 默认是最大堆
9     * @param {Function} cmp
10     */
11    constructor(cmp = defaultCmp) {
12        this.container = [];
13        this.cmp = cmp;
14    }
15
16    insert(data) {
17        const { container, cmp } = this;
18
19        container.push(data);
20        let index = container.length - 1;
21        while (index) {
22            let parent = Math.floor((index - 1) / 2);
23            if (!cmp(container[index], container[parent])) {
24                return;
25            }
26            swap(container, index, parent);
27            index = parent;
28        }
29    }
30
31    extract() {
32        const { container, cmp } = this;
33        if (!container.length) {
34            return null;
35        }
36
37        swap(container, 0, container.length - 1);
38        const res = container.pop();
39        const length = container.length;
40        let index = 0,
41            exchange = index * 2 + 1;
42
43        while (exchange < length) {
44            // // 以最大堆的情况来说：如果有右节点，并且右节点的值大于左节点的值
45            let right = index * 2 + 2;
46            if (right < length && cmp(container[right], container[exchange])) {
47                exchange = right;
48            }
49            if (!cmp(container[exchange], container[index])) {
50                break;
51            }
52            swap(container, exchange, index);
53            index = exchange;
54            exchange = index * 2 + 1;
55        }
56
57        return res;
58    }
59
60    top() {
61        if (this.container.length) return this.container[0];
62        return null;
63    }
64}

整体的代码逻辑如下：

复制
1
2var MedianFinder = function() {
3    this.maxHeap = new Heap();
4    this.minHeap = new Heap((x, y) => x < y);
5};
6
7MedianFinder.prototype.addNum = function(num) {
8    this.maxHeap.insert(num);
9    this.minHeap.insert(this.maxHeap.top());
10    this.maxHeap.extract();
11
12    if (this.maxHeap.container.length < this.minHeap.container.length) {
13        this.maxHeap.insert(this.minHeap.top());
14        this.minHeap.extract();
15    }
16};
17
18MedianFinder.prototype.findMedian = function() {
19    return this.maxHeap.container.length > this.minHeap.container.length
20        ? this.maxHeap.top()
21        : (this.maxHeap.top() + this.minHeap.top()) / 2;
22};

时间复杂度是O(logN)，空间复杂度是O(N)。