迹忆客 专注技术分享

当前位置:主页 > 学无止境 > 编程语言 > C++ >

用 C++ 计算运行中位数

作者:迹忆客 最近更新:2023/08/25 浏览次数:

这是有关如何有效计算运行中位数的文章。 我们将从运行中位数的详细描述开始,然后是算法和一些实现注意事项。


运行中位数

运行中位数是计算数字序列的有效方法。 其背后的直觉是,如果我们对中位数感兴趣,那么我们不需要知道序列中的所有值,而是可以跟踪有多少值高于或低于它。

如果有偶数个值,那么我们将取两半的平均值(或均值)并将其用作新的中间值。

运行中位数从排序列表中间的观察值开始。 将下一个观察结果与中间的观察结果进行比较; 如果它更大或更小,它就成为新的中间点。

此过程持续进行,直到排序列表中不再有任何观察结果为止。


用 C++ 计算运行中位数

运行中位数是使用两个堆计算的。 所有小于或等于当前中位数的值都位于左堆中。

所有大于或等于当前中位数的都位于右侧堆中。

通过交换这两个堆中的每个数字来更新运行中位数。 为了维持恒定数量的交换,我们需要一种方法来知道这两个堆中的一个何时变空。

当这两个堆之一变空时,意味着所有小于或等于当前中位数的值都已被处理,并且所有大于或等于当前中位数的值都已被处理。 此时,我们可以与不为空的堆中的值进行交换,该值始终是左堆或正确的堆,具体取决于哪个堆先被清空。

我们需要一个支持两端高效插入和删除的数据结构才能使该算法发挥作用。 该数据结构还应该能够利用缓存局部性。

转载请发邮件至 1244347461@qq.com 进行申请,经作者同意之后,转载请以链接形式注明出处

本文地址:

相关文章

Arduino 中停止循环

发布时间:2024/03/13 浏览次数:444 分类:C++

可以使用 exit(0),无限循环和 Sleep_n0m1 库在 Arduino 中停止循环。

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()函数在串口监视器上显示变量值。

Arduino if 语句

发布时间:2024/03/13 浏览次数:123 分类:C++

可以使用 if 语句检查 Arduino 中的不同条件。

Arduino ICSP

发布时间:2024/03/13 浏览次数:214 分类:C++

ICSP 引脚用于两个 Arduino 之间的通信以及对 Arduino 引导加载程序进行编程。

使用 C++ 编程 Arduino

发布时间:2024/03/13 浏览次数:127 分类:C++

本教程将讨论使用 Arduino IDE 在 C++ 中对 Arduino 进行编程。

Arduino 中的子程序

发布时间:2024/03/13 浏览次数:168 分类:C++

可以通过在 Arduino 中声明函数来处理子程序。

扫一扫阅读全部技术教程

社交账号
  • https://www.github.com/onmpw
  • qq:1244347461

最新推荐

教程更新

热门标签

扫码一下
查看教程更方便