对于数据流,对应的就是在线算法了,一道很经典的题目就是在1亿个数中找到最大的前100个数,这是一道堆应用题,找最大的前100个数,那么我们就创建一个大小为100的最小化堆,每来一个元素就与堆顶元素比较,因为堆顶元素是目前前100大数中的最小数,前来的元素如果比该元素大,那么就把原来的堆顶替换掉。
那么对于这一道题呢?如果单纯的把所有元素放到一个数组里,每次查找中位数最快也要o(n),综合下来是o(n^2)的复杂度。我们可以利用上面例子中的想法,用一个最大堆来维护当前前n/2小的元素,那么每次找中位数只到取出堆顶就可以了。但是,有一个问题,数据要动态增长,有可能之前被替换掉的元素随着元素的增加又跑回来了,所以我们不能单纯得向上题一样把元素丢掉,我们可以再用一个最小化堆来存前n/2大的元素。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605211.html