用 C++ 计算运行中位数
这是有关如何有效计算运行中位数的文章。 我们将从运行中位数的详细描述开始,然后是算法和一些实现注意事项。
运行中位数
运行中位数是计算数字序列的有效方法。 其背后的直觉是,如果我们对中位数感兴趣,那么我们不需要知道序列中的所有值,而是可以跟踪有多少值高于或低于它。
如果有偶数个值,那么我们将取两半的平均值(或均值)并将其用作新的中间值。
运行中位数从排序列表中间的观察值开始。 将下一个观察结果与中间的观察结果进行比较; 如果它更大或更小,它就成为新的中间点。
此过程持续进行,直到排序列表中不再有任何观察结果为止。
用 C++ 计算运行中位数
运行中位数是使用两个堆计算的。 所有小于或等于当前中位数的值都位于左堆中。
所有大于或等于当前中位数的都位于右侧堆中。
通过交换这两个堆中的每个数字来更新运行中位数。 为了维持恒定数量的交换,我们需要一种方法来知道这两个堆中的一个何时变空。
当这两个堆之一变空时,意味着所有小于或等于当前中位数的值都已被处理,并且所有大于或等于当前中位数的值都已被处理。 此时,我们可以与不为空的堆中的值进行交换,该值始终是左堆或正确的堆,具体取决于哪个堆先被清空。
我们需要一个支持两端高效插入和删除的数据结构才能使该算法发挥作用。 该数据结构还应该能够利用缓存局部性。
相关文章
Arduino 复位
发布时间:2024/03/13 浏览次数:315 分类:C++
-
可以通过使用复位按钮,Softwarereset 库和 Adafruit SleepyDog 库来复位 Arduino。
Arduino 的字符转换为整型
发布时间:2024/03/13 浏览次数:181 分类:C++
-
可以使用简单的方法 toInt()函数和 Serial.parseInt()函数将 char 转换为 int。
Arduino 串口打印多个变量
发布时间:2024/03/13 浏览次数:381 分类:C++
-
可以使用 Serial.print()和 Serial.println()函数在串口监视器上显示变量值。