程序员经验分享-hwhale

如何找到数组中至少重复N/2次的元素？

2023-11-27

给定一个包含 N 个元素的数组。我们知道其中一个元素至少重复 N/2 次。

我们对其他元素一无所知。它们可能是重复的，也可能是唯一的。

有没有办法找出单次重复至少 N/2 次或者可能是 O(N) 的元素？

无需使用额外空间。


由于其他用户已经发布了该算法，我不再重复。不过，我提供了一个关于其工​​作原理的简单解释：

考虑下图，它实际上是非偏振光的图：

arrows radiating from the centre

从中心开始的每个箭头代表不同的候选人。想象一下箭头上的某个点代表计数器和候选者。最初计数器为零，因此它从中心开始。
当找到当前候选者时，它会朝该箭头的方向移动一步。如果发现不同的值，计数器将向中心移动一步。
如果存在多数值，则超过一半的移动将朝向该箭头，因此算法将以当前候选值作为多数值结束。

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

c

Algorithm

如何找到数组中至少重复N/2次的元素？ 的相关文章

随机推荐

  • 使用 HTTP Post 从客户端流式传输数据

    我想将数据从客户端流式传输到服务器 我的应用程序将音频数据流式传输到服务器 当我开始流式传输时 我不知道音频会持续多长时间 我想通过在记录数据时传输数据来减少延迟 一旦所有数据上传完毕 我就会对其进行处理 所以 我想要的是一个 HTTP P

  • 如何在 UWP 应用中保留 TextBlock 的空白

    如果您只是将 TextBlock 中的 Text 属性的值设置为 例子 请注意 此处有 3 个空格end这个字符串 TextBlock 在 UI 中显示的只是 Example 并且在网上搜索解决方案后 发现有一种方法可以解决这个问题

  • 如何用 C++ 读取和解析 CSV 文件？

    我需要在 C 中加载和使用 CSV 文件数据 此时它实际上可以只是一个逗号分隔的解析器 即不用担心转义新行和逗号 主要需要是一个逐行解析器 每次调用该方法时 它将返回下一行的向量 我发现这篇文章看起来很有前途 http www boost

  • javascript，在开始颜色和结束颜色之间选择一个随机的十六进制颜色

    有什么快速的方法可以实现这一点吗 例如 起始颜色 EEEEEE 和结束颜色 FFFFFF 会产生类似 FEFFEE 的颜色 当然 十六进制被编码为数字 但要使其有意义 您必须首先提取 rgb 组件 function rgb string r

  • php邮件的smtp配置

    我使用 php 邮件功能从我的网站发送邮件 但现在它不起作用 我联系了我们的托管团队 然后他们告诉我使用 smtp 因为他们对服务器做了一些更改 我不知道该怎么做 当前代码 带有 php 邮件功能 如下 任何人都可以帮助我进行与此相关的更改

  • Go 闭包在内存中是如何布局的？

    有关闭包的一般解释 请参见JavaScript 闭包如何工作 Go 闭包到底是如何在内存中布局的 以以下函数为例 type M int func m M Adder amount int func return func m m amoun

  • FileHelpers 和 CSV：当记录可以无限水平扩展时该怎么办

    我正在尝试使用 FileHelpers 解析这种类型的 CSV 文件 Tom 1 2 3 4 5 6 7 8 9 10 Steve 1 2 3 Bob 1 2 3 4 5 6 Cthulhu 1 2 3 4 5 Greg 1 2 3 4 5

  • 使用 Scikit Learn 的 DictVectorizer 时出现 toarray 内存错误

    我正在尝试对我的数据实施 SelectKBest 算法 以从中获得最佳功能 为此 我首先使用 DictVectorizer 预处理数据 该数据由 1061427 行和 15 个特征组成 每个功能都有许多不同的值 我相信由于高基数我遇到了内存

  • java 电话号码验证

    这是我的问题 为电话号码创建一个构造函数 给定本地号码的 xxx xxx xxxx 或 xxx xxxx 形式的字符串 如果格式无效 则抛出异常 所以我想使用正则表达式来验证它 但我不知道我做得是否正确 另外我必须抛出什么样的异常 我需要创

  • Gitlab 屏蔽变量

    我似乎无法屏蔽 Gitlab CI 上的变量 我正在尝试上传 ssh 私钥 但无论我做什么 它都拒绝屏蔽它 那是我正在尝试存储私钥在 Gitlab 上供我的生产服务器拥有公钥的 Gitlab 运行程序使用 我不是问如何在构建过程中将其介绍给

  • 詹金斯作业重启后消失

    我在 Jenkins 1 5 31 中遇到这个奇怪的问题 我已经配置了 Maven 作业 我仍然在 Jenkins Home 目录中看到它 尽管我仍然可以通过默认端口 8080 访问 Jenkins 但我的 Jenkins Windows

  • 如何在gdb中打印-0x4(%rbp)？

    反汇编中有这样的代码 movl 0x6 0x4 rbp 我尝试以这种方式打印该值但失败 gdb p 0x4 esp A syntax error in expression near esp gdb p 0x4 esp Argument t

  • 为什么我的dispatch_once会陷入僵局？

    为什么我会陷入僵局 void foo static dispatch once t onceToken dispatch once onceToken self foo whatever 我预计foo第一次调用时执行两次 现有的答案都不是很

  • MCrypt rijndael-256 到 OpenSSL aes-256-ecb 转换

    由于 Mcrypt 已被弃用 我想在代码中使用 OpenSSL 因为我们已经在服务器中使用 php 7 2 4 我使用以下代码进行加密 解密 加密 function encrypt text salt if text return if s

  • 增加 EWS 流订阅连接的生命周期元素

    使用 Microsoft 的 EWS 我们能够监听邮箱并在收到新电子邮件时采取行动 但是 我不知道如何避免连接超时 根据 Microsoft 的说法 以下是 StreamingSubscriptionConnection 的构造函数 pub

  • django模板系统，调用模型内的函数

    我想在模板中调用模型中的函数 例如 class ChannelStatus models Model def get related deltas self epk mystring if not self get error code d

  • 将信息从 Chromium Embedded (Javascript) 发送到包含 C++ 的应用程序

    查看 Chromium 嵌入式框架示例后 我有一个问题 我需要与窗口的嵌入部分进行本机交互 然而 在 CEF 示例中 我看到的只是 c 向浏览器发送消息 而不是相反 我想知道是否有任何方法可以从 JavaScript 从 C 发送消息 就像

  • R 将因子 ID 变量转换为数字 ID 变量

    我对 R 编程有疑问 在花了几个小时查看互联网和 Stack Overflow 上的潜在响应后 我不知道如何解决它 我在 data frame 的一列中有一个因子变量 如下所示 Columnname agsgssg agsgssg agsg

  • 将设备中的磁场 X、Y、Z 值转换为全局参考系

    当您使用 TYPE MAGNETOMETER 传感器时 您将获得与设备方向相关的磁场强度的 X Y Z 值 我想要得到的是将这些值转换为全局参考系 澄清 用户拿起设备 测量这些值 然后将设备绕任何轴旋转一定角度并获得相同的值 请在下面找到类

  • 如何找到数组中至少重复N/2次的元素？

    给定一个包含 N 个元素的数组 我们知道其中一个元素至少重复 N 2 次 我们对其他元素一无所知 它们可能是重复的 也可能是唯一的 有没有办法找出单次重复至少 N 2 次或者可能是 O N 的元素 无需使用额外空间 由于其他用户已经发布了该

热门标签