程序员面试的那些小事架构算法设计模式和编程理论程序员

lintcode 数据流中位数

2017-01-16  本文已影响179人  yzawyx0220

数字是不断进入数组的,在每次添加一个新的数进入数组的同时返回当前新数组的中位数。

您在真实的面试中是否遇到过这个题? Yes
说明
中位数的定义:

中位数是排序后数组的中间值,如果有数组中有n个数,则中位数为A[(n-1)/2]。
比如:数组A=[1,2,3]的中位数是2,数组A=[1,19]的中位数是1。
样例
持续进入数组的数的列表为:[1, 2, 3, 4, 5],则返回[1, 1, 2, 2, 3]

持续进入数组的数的列表为:[4, 5, 1, 3, 2, 6, 0],则返回 [4, 4, 4, 3, 3, 3, 3]

持续进入数组的数的列表为:[2, 20, 100],则返回[2, 2, 20]
题目链接:http://www.lintcode.com/zh-cn/problem/data-stream-median/
维护一个最大堆和最小堆,其中最大堆来保存数组中较小的一半的数,最小堆保存较大的另一半数。当元素为数组的奇数个时,插入到最大堆中,元素为数组的偶数个时,插入到最小堆中,这样,最大堆的堆顶即为中位数。

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: The median of numbers
     */
    vector<int> medianII(vector<int> &nums) {
        // write your code here
        multiset<int> left,right;
        vector<int> res;
        bool flag = true;
        for (int i : nums) {
            int temp = i;
            if (flag) {
                if (!right.empty() && i > *right.begin()) {
                    right.insert(i);
                    temp = *right.begin();
                    right.erase(right.find(temp));
                }
                left.insert(temp);
            }
            else {
                if (!left.empty() && i < *left.rbegin()) {
                    left.insert(i);
                    temp = *left.rbegin();
                    left.erase(left.find(temp));
                }
                right.insert(temp);
            }
            flag = !flag;
            res.push_back(*left.rbegin());
        }
        return res;
    }
};
上一篇下一篇

猜你喜欢

热点阅读