程序员经验分享-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 次的元素 的相关文章

  • 编译时运算符

    有人可以列出 C 中可用的所有编译时运算符吗 C 中有两个运算符 无论操作数如何 它们的结果始终可以在编译时确定 它们是sizeof 1 and 2 当然 其他运算符的许多特殊用途可以在编译时解决 例如标准中列出的那些整数常量表达式 1 与

  • EF Core Group By 翻译支持条件总和

    听说 EF Core 2 1 将支持翻译小组 我感到非常兴奋 我下载了预览版并开始测试它 但发现我在很多地方仍然没有得到翻译分组 在下面的代码片段中 对 TotalFlagCases 的查询将阻止翻译分组工作 无论如何 我可以重写这个以便我

  • 通过 CMIS (dotCMIS) 连接到 SP2010：异常未经授权

    我正在使用 dotCMIS 并且想要简单连接到我的 SP2010 服务器 我尝试用 C 来做到这一点 如下所示http chemistry apache org dotnet getting started with dotcmis htm

  • WCF RIA 服务 - 加载多个实体

    我正在寻找一种模式来解决以下问题 我认为这很常见 我正在使用 WCF RIA 服务在初始加载时将多个实体返回给客户端 我希望两个实体异步加载 以免锁定 UI 并且我想利用 RIA 服务来执行此操作 我的解决方案如下 似乎有效 这种方法会遇到

  • Asp.NET WebApi 中类似文件名称的路由

    是否可以在 ASP NET Web API 路由配置中添加一条路由 以允许处理看起来有点像文件名的 URL 我尝试添加以下条目WebApiConfig Register 但这不起作用 使用 URIapi foo 0de7ebfa 3a55

  • BitTorrent 追踪器宣布问题

    我花了一点业余时间编写 BitTorrent 客户端 主要是出于好奇 但部分是出于提高我的 C 技能的愿望 我一直在使用理论维基 http wiki theory org BitTorrentSpecification作为我的向导 我已经建

  • 如何使用 ICU 解析汉字数字字符？

    我正在编写一个使用 ICU 来解析由汉字数字字符组成的 Unicode 字符串的函数 并希望返回该字符串的整数值 五 gt 5 三十一 gt 31 五千九百七十二 gt 5972 我将区域设置设置为 Locale getJapan 并使用

  • 不同枚举类型的范围和可转换性

    在什么条件下可以从一种枚举类型转换为另一种枚举类型 让我们考虑以下代码 include

  • 在 ASP.NET 5 中使用 DI 调用构造函数时解决依赖关系

    Web 上似乎充斥着如何在 ASP NET 5 中使用 DI 的示例 但没有一个示例显示如何调用构造函数并解决依赖关系 以下只是众多案例之一 http social technet microsoft com wiki contents a

  • C# 中通过 Process.Kill() 终止的进程的退出代码

    如果在我的 C 应用程序中 我正在创建一个可以正常终止或开始行为异常的子进程 在这种情况下 我通过调用 Process Kill 来终止它 但是 我想知道该进程是否已退出通常情况下 我知道我可以获得终止进程的错误代码 但是正常的退出代码是什

  • 如何查看网络连接状态是否发生变化？

    我正在编写一个应用程序 用于检查计算机是否连接到某个特定网络 并为我们的用户带来一些魔力 该应用程序将在后台运行并执行检查是否用户请求 托盘中的菜单 我还希望应用程序能够自动检查用户是否从有线更改为无线 或者断开连接并连接到新网络 并执行魔

  • 覆盖子类中的字段或属性

    我有一个抽象基类 我想声明一个字段或属性 该字段或属性在从该父类继承的每个类中具有不同的值 我想在基类中定义它 以便我可以在基类方法中引用它 例如覆盖 ToString 来表示 此对象的类型为 property field 我有三种方法可以

  • 为什么编译时浮点计算可能不会得到与运行时计算相同的结果？

    In the speaker mentioned Compile time floating point calculations might not have the same results as runtime calculation

  • 通过指向其基址的指针删除 POD 对象是否安全？

    事实上 我正在考虑那些微不足道的可破坏物体 而不仅仅是POD http en wikipedia org wiki Plain old data structure 我不确定 POD 是否可以有基类 当我读到这个解释时is triviall

  • 如何在Xamarin中删除ViewTreeObserver？

    假设我需要获取并设置视图的高度 在 Android 中 众所周知 只有在绘制视图之后才能获取视图高度 如果您使用 Java 有很多答案 最著名的方法之一如下 取自这个答案 https stackoverflow com a 24035591

  • 混合 ExecutionContext.SuppressFlow 和任务时 AsyncLocal.Value 出现意外值

    在应用程序中 由于 AsyncLocal 的错误 意外值 我遇到了奇怪的行为 尽管我抑制了执行上下文的流程 但 AsyncLocal Value 属性有时不会在新生成的任务的执行范围内重置 下面我创建了一个最小的可重现示例来演示该问题 pr

  • C# 模拟VolumeMute按下

    我得到以下代码来模拟音量静音按键 DllImport coredll dll SetLastError true static extern void keybd event byte bVk byte bScan int dwFlags

  • C# - OutOfMemoryException 在 JSON 文件上保存列表

    我正在尝试保存压力图的流数据 基本上我有一个压力矩阵定义为 double pressureMatrix new double e Data GetLength 0 e Data GetLength 1 基本上 我得到了其中之一pressur

  • Windows 和 Linux 上的线程

    我在互联网上看到过在 Windows 上使用 C 制作多线程应用程序的教程 以及在 Linux 上执行相同操作的其他教程 但不能同时用于两者 是否存在即使在 Linux 或 Windows 上编译也能工作的函数 您需要使用一个包含两者的实现

  • 如何在文本框中插入图像

    有没有办法在文本框中插入图像 我正在开发一个聊天应用程序 我想用图标图像更改值 等 但我找不到如何在文本框中插入图像 Thanks 如果您使用 RichTextBox 进行聊天 请查看Paste http msdn microsoft co

随机推荐

  • 无法注册 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

热门标签