程序员经验分享-hwhale

O(n) 算法找出出现次数超过 n/2 次的元素

2024-01-11

在一次采访中，有人要求我提供一个 O(n) 算法来打印在数组中出现超过 n/2 次的元素（如果存在这样的元素）。 n 是数组的大小。 我不知道如何做到这一点。有人可以帮忙吗？


这是博耶的投票算法 http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html.

在太空中也是 O(1)！

Edit

对于那些抱怨网站配色方案的人（像我一样）......这是原始论文 http://www.cs.utexas.edu/users/boyer/mjrty.ps.Z.

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

c

O(n) 算法找出出现次数超过 n/2 次的元素 的相关文章

随机推荐

  • 无法注册 BoringSSL 日志调试更新

    当在安装了 iOS 11 beta 的 iPhone 上运行时 在 Xcode 9 beta 中调试应用程序时 我在执行网络调用时开始注意到以下消息 network config register boringssl log debug u

  • FB Realtime API 没有/不一致地通知某些连接（音乐、电影、书籍、电视）

    我目前遇到了 Facebook 实时 API 的问题 我希望订阅用户个人资料上的许多内容 包括他们在音乐 书籍 电视和电影类别中的 喜欢 当我通过 FQL 和图表查询时 我得到了正确的信息 但当用户个人资料上的这些条目发生更改时 Faceb

  • 用于编辑模型的 Django 表单向导

    我有一个 Django 表单向导 可以很好地为我的模型之一创建内容 我想使用相同的向导来编辑现有内容的数据 但找不到如何执行此操作的好示例 这是我的项目代码的简化版本 forms py class ProjectEssentialsForm

  • VS Code 找不到 pytest 测试

    我在 vs code 中设置了 PyTest 但即使从命令行运行 pytest 工作正常 也没有找到任何测试 我正在使用 MiniConda 和 Python 3 6 6 虚拟环境在 Win10 上开发 Django 应用程序 VS Cod

  • 选择刚刚单击的项目的下一个同级项

    我有一个ul其中包含图像 这些图像是从 Twitter 获取的个人资料图像并附加到ul动态地 一旦用户单击任何图像 我还需要缓存紧邻该图像的节点 下一个兄弟 我尝试使用next 选择器如下所示 但控制台中记录的是一条我不明白的消息 这是代码

  • 手动触发的 cron 作业可以遵守并发策略吗？

    所以我有一个这样的 cron 工作 apiVersion batch v1beta1 kind CronJob metadata name my cron job spec schedule 0 0 31 2 failedJobsHisto

  • Rcpp：安装带有静态库的包，以便独立于平台使用

    我想使用libDAI C https bitbucket org jorism libdaiR 包中的库并需要该包 可在 Linux 和 Windows 上使用 节省磁盘空间 外部库有约 60 Mb 最终用户不需要安装boost和gmp进行

  • 更新后程序会自行重启

    我到处都检查过 所以希望不会重复问题 我想为我正在编写的一些 C 代码添加可移植更新功能 该程序可能不在任何特定位置 我更愿意将其保留为单个二进制文件 无动态库加载 然后更新完成后 我希望程序能够重新启动 不是循环 实际上是从硬盘重新加载

  • Heroku 应用程序因数据库崩溃

    我的代码在本地可以工作 但是当我尝试在 Heroku 上运行它时 它不起作用 我在 Heroku 上添加了一个数据库 但它仍然无法工作 有任何线索说明为什么会发生这种情况吗 import sys import os from flask i

  • Google+ 代码片段缩略图未显示

    我的网站中有 google 代码片段 要在 google 上分享我的网站 我的代码如下所示

  • iOS9 中的应用程序传输安全和 IP 地址

    我使用在我的开发盒上运行的本地服务器来开发我的 iOS 应用程序 在设备上进行测试时 我直接通过 IP 地址进行连接 该地址通过 HTTP 而不是 HTTPS 因此我不必在开发过程中处理自签名证书 而设备根本不喜欢自签名证书 我认为这就足够

  • JSF 转换器时间戳

    我想将我的输入转换为时间戳值 我只在示例中找到了日期转换器 有没有最佳实践 谢谢 Update 我想保存用户的生日 但我的后端需要时间戳值 我在将它绑定到我的 jsf 前端时遇到问题 也许示例链接会有帮助 我尝试如下 public void

  • 边缘线和填充 matplotlib 或 seaborn 分布图的不同透明度

    我想为我在 matplotlib seaborn 中创建的分布图的边缘线和填充设置不同级别的透明度 alpha 例如 ax1 sns distplot BSRDI DF label BsrDI bins newBins kde False

  • 如何使用 sed 删除与模式匹配的行及其后面的行？

    我有一个看起来像这样的文件 good text good text FLAG bad text bad text good text good text good test bad Text FLAG bad text bad text g

  • 我是否缺少在 Ubuntu 9.04 上使用 Python2.6 绑定构建/安装 VTK-5.4 的步骤？

    我使用源代码的 Python 绑定成功构建并安装了 VTK 5 4 然而 当我尝试在 python 中导入 VTK 时 它给出了以下回溯错误 文件 第 1 行 位于 文件 usr local lib python2 6 dist packa

  • 如何在 swift 3 中将 NSArray 转换为 Swift Array

    我有两个数组 var arr1 NSArray var arr2 String 我想转换NSArray到字符串数组中 我在用 arr2 arr1 作为 细绳 但它给了我错误 NSString is not a subtype of NSAr

  • 在 Python 中将小时和分钟转换为总分钟

    我有一个 Pandas DataFrame 其中有一列以小时和分钟为单位的时间字符串 例如 1 小时 8 分钟 有些单元只有几分钟 例如 47 分钟 我试图从这种格式转换为总分钟数的整数值 例如 1 小时 8 分钟将是 68 我尝试对其进行

  • TFS 2018 Update 2 IIS 网站部署已弃用或缺失

    将 TFS 更新到更新 2 后 在 CI 构建任务中 IIS Web 应用程序部署 被标记为 已弃用 这个任务的替代品是什么 Also in the CD in the after adding IIS Website Deployment

  • Django 无效的块标签：endelse 和 ifequal

    我想使用 djangoifequal and else判断变量是否等于的标签80 or 22 所以 这是代码 if firewalls thead tr th IP address th th Function th tr thead en

  • O(n) 算法找出出现次数超过 n/2 次的元素

    在一次采访中 有人要求我提供一个 O n 算法来打印在数组中出现超过 n 2 次的元素 如果存在这样的元素 n 是数组的大小 我不知道如何做到这一点 有人可以帮忙吗 这是博耶的投票算法 http www cs utexas edu moor

热门标签