那些读过我之前问题的人都知道我在理解和实现快速排序和快速选择方面的工作,以及其他一些基本算法.
Quickselect用于计算未排序列表中的第k个最小元素,此概念也可用于查找未排序列表中的中位数.
这一次,我需要帮助设计一种有效的技术来计算运行中位数,因为快速选择不是一个好的选择,因为它需要在每次列表更改时重新计算.因为quickselect必须每次都重新启动,所以它不能利用先前的计算,所以我正在寻找一种类似(可能)但在运行中位数方面更有效的不同算法.
我试图排序并找到一个只包含3到4个不同整数的整数字符串的中位数.
我正在处理的数字量大约为2千万到2千5百万,我应该对向量进行排序,每次将新整数添加到向量中时找到中位数,并将中位数添加到单独的"总计"变量中每次生成中位数时,它会汇总所有中位数.
1 Median: 1 Total: 1
1 , 2 Median: (1+2)/2 = 1 Total: 1 + 1 = 2
1 , 2 , 3 Median: 2 Total: 2 + 2 = 4
1 , 1 , 2 , 3 Median: (1+2)/2 = 1 Total: 4 + 1 = 5
1 , 1 , 1 , 2 , 3 Median: 1 Total: 5 + 1 = 6
我试图找到一种方法来进一步优化我的代码,因为它不够高效.(必须在2s左右处理)有没有人知道如何进一步加快我的代码逻辑？
我目前在C++中使用2个堆或优先级队列.一个用作最大堆,另一个用作最小堆.
从数据结构中找到了寻找中位数的想法
You can use 2 heaps, that we will …