剑指offer-数据流中的中位数

数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。

示例:

输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

思路

这里为了方便，使用排序数组（排序链表也是类似）来实现；最快的实现应该是使用两个堆来实现；

1 addNum 插入数组完毕后，需要对数组重新排序

2 当数组的长度是奇数时，中位数是 mid = array.length » 1,即结果是 array[mid]；当数组的长度是偶数时，中位数是mid = array.length » 1，结果为 (array[mid-1] + array[mid]) / 2;

代码

/**
 * initialize your data structure here.
 */
var MedianFinder = function() {
    // 思路，使用排序的数组，保证插入的时候O(nlogn)，寻找中位数的时候O(1)
    this.arr = [];
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function(num) {
    this.arr.push(num);
    this.arr.sort((a, b) => a-b);
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function() {
    const isEven = this.arr.length % 2 === 0;
    const mid = this.arr.length >> 1;
    if (isEven) {
        return (this.arr[mid-1] + this.arr[mid]) / 2;
    }
    return this.arr[mid];
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * var obj = new MedianFinder()
 * obj.addNum(num)
 * var param_2 = obj.findMedian()
 */

复杂度分析

时间复杂度: O(NlogN)
空间复杂度: O(N)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG 科学上网工具

数据流中的中位数

思路

代码

复杂度分析

CATALOG

FEATURED TAGS

FRIENDS