字节青训Marscode——8:找出整形数组中超过一半的数

问题描述

小R从班级中抽取了一些同学,每位同学都会给出一个数字。已知在这些数字中,某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。


测试样例

样例1:

输入:array = [1, 3, 8, 2, 3, 1, 3, 3, 3]
输出:3

样例2:

输入:array = [5, 5, 5, 1, 2, 5, 5]
输出:5

样例3:

输入:array = [9, 9, 9, 9, 8, 9, 8, 8]
输出:9

步骤1:问题定义与分析

题目要求:

从一个整数数组 array 中找出某个出现次数超过数组长度一半的数字,保证这样的数字一定存在。

输入与输出:
  • 输入:一个整数数组 array,长度为 n
  • 输出:数组中某个出现次数超过 n / 2 的数字。
限制与边界条件:
  1. 数组中保证一定存在满足条件的数字。
  2. 数组长度 n 的范围未明确给出,但假设为合理范围(如 1 <= n <= 10^6)。
  3. 只需要输出符合条件的任意一个数字,不需要处理无解的情况。
问题性质:
  • 根据题意,某个数字的出现次数超过总数的一半,称为 多数元素
  • 这种问题可以通过经典的算法(如摩尔投票法)高效解决,而不需要使用暴力计数法。

步骤2:算法设计与分析

方法1:哈希表计数
  • 使用哈希表统计每个数字的出现次数。
  • 遍历数组,当某个数字的出现次数超过 n / 2 时返回该数字。
时间复杂度与空间复杂度:
  • 时间复杂度:O(n),需要遍历数组。
  • 空间复杂度:O(n),存储哈希表。
适用场景

适用于小规模数据,且有足够的内存空间支持额外的哈希表存储。


方法2:摩尔投票法(最佳选择)

摩尔投票法是一种高效的线性时间算法,专门用于解决多数元素问题。

算法步骤:
  1. 初始化一个候选值 candidate 和计数器 count 为 0。
  2. 遍历数组:
    • 如果当前计数为 0,将当前数字设置为候选值 candidate,并将计数器设置为 1。
    • 如果当前数字等于 candidate,计数器加 1。
    • 如果当前数字不等于 candidate,计数器减 1。
  3. 遍历结束时,candidate 即为多数元素。
时间复杂度与空间复杂度:
  • 时间复杂度:O(n),只需遍历数组一次。
  • 空间复杂度:O(1),不需要额外的存储空间。
适用场景

适用于任何规模的数据,且是本问题的最佳解决方案。

摩尔投票法原理解释

摩尔投票法(Boyer-Moore Voting Algorithm)是一种高效的算法,用于在一个数组中找到出现次数超过一半的元素(即 多数元素)。它的核心思想是通过一种计数机制,利用元素的多数性来进行筛选,最终在 O(n) 的时间复杂度内找到目标元素,并且空间复杂度为 O(1)。

问题背景

在一个大小为 n 的数组中,假设存在一个数字的出现次数超过 n / 2,也就是说这个数字是多数元素。摩尔投票法的目标是找出这个元素。通过遍历数组一次并利用投票机制,我们能够在常数空间内找到这个元素。

摩尔投票法的基本原理
  1. 计数器: 摩尔投票法通过维护一个计数器来识别出现次数最多的元素。这个计数器会随着遍历数组而动态调整。

  2. 选举过程

    • 候选人:首先,我们假设某个元素是候选人(candidate),并初始化计数器为 0。
    • 投票规则
      • 如果当前计数器为 0,选择当前元素作为新的候选人,并将计数器设置为 1。
      • 如果当前元素与候选人相同,计数器加 1。
      • 如果当前元素与候选人不同,计数器减 1。

    这种“投票”方式能够抵消一些非多数元素的干扰,并最终得到一个可能是多数元素的候选值。

  3. 计数的终结: 当整个数组遍历完成后,candidate 就是候选的多数元素。由于多数元素的出现次数超过了数组长度的一半,这个候选元素一定就是多数元素。

详细步骤
  1. 初始化

    • candidate(候选元素)初始化为一个任意值。
    • count(计数器)初始化为 0。
  2. 遍历数组

    • 对于数组中的每个元素:
      • 如果 count == 0,选择当前元素作为新的候选元素,并将计数器设为 1。
      • 如果当前元素等于 candidate,则增加计数器。
      • 如果当前元素与 candidate 不同,则减少计数器。
  3. 返回结果

    • 遍历结束后,candidate 即为数组中出现次数最多的元素。
直观解释

假设数组中的多数元素出现次数超过了数组总长度的一半(n/2)。在摩尔投票法中,元素的“投票”机制确保了最多的元素最终会“胜出”。具体来说:

  • 当遇到与当前候选人不同的元素时,我们会减去一个计数,导致非多数元素的出现机会被“削弱”。
  • 只有当某个元素的出现次数非常高时,才可能在整个数组中最终成为唯一的候选人。
举例说明

假设我们有数组:[3, 3, 4, 2, 4, 4, 2, 4, 4]

  • 第一步:candidate = 3, count = 0
    • 看到第一个元素 3count = 1candidate = 3
    • 看到第二个元素 3count = 2candidate = 3
    • 看到第三个元素 4count = 1candidate = 3count--)。
    • 看到第四个元素 2count = 0candidate = 2count = 1)。
    • 看到第五个元素 4count = 2candidate = 4
    • ...
    • 遍历完成后,candidate = 4 是多数元素。
为什么摩尔投票法有效?
  • 由于题目保证了多数元素一定存在,并且它的出现次数超过数组的一半,因此,在摩尔投票法中,不同的元素相互“抵消”掉的次数是对等的,最终剩下的就是多数元素。
  • 当计数器归零时,说明当前候选元素被其他元素“抵消”了,我们就将候选元素换成新的元素,从而不断减少非多数元素的影响,直到最后剩下的候选元素必然是多数元素。

摩尔投票法的优势

  1. 时间复杂度 O(n)

    • 只需要遍历数组一次,因此时间复杂度是 O(n),其中 n 是数组的长度。
  2. 空间复杂度 O(1)

    • 只使用了两个变量:candidatecount,因此空间复杂度是 O(1),不需要额外的空间。
  3. 适用于大规模数据

    • 在大规模数据中,摩尔投票法具有很高的效率,特别是在内存和空间限制较大的情况下,能够以最优的时间和空间复杂度完成任务。

步骤3:C++ 代码实现

使用摩尔投票法解决问题:

#include <iostream>
#include <vector>using namespace std;int solution(vector<int> array) {// 摩尔投票法int candidate = 0; // 候选元素int count = 0;      // 计数器// 第一次遍历,确定候选元素for (int num : array) {if (count == 0) {candidate = num; // 重置候选元素count = 1;       // 初始化计数器} else if (num == candidate) {count++; // 当前数字等于候选元素,计数器加1} else {count--; // 当前数字不等于候选元素,计数器减1}}// 此时candidate即为超过一半的数字,直接返回return candidate;
}int main() {// 测试用例cout << (solution({1, 3, 8, 2, 3, 1, 3, 3, 3}) == 3) << endl; // 输出 1 (True)cout << (solution({5, 5, 5, 1, 2, 5, 5}) == 5) << endl;       // 输出 1 (True)cout << (solution({9, 9, 9, 9, 8, 9, 8, 8}) == 9) << endl;   // 输出 1 (True)return 0;
}
代码解释:
  1. candidate:记录当前的候选多数元素。
  2. count:记录候选元素的计数。
  3. 第一遍遍历:通过计数器逻辑,找出候选元素。
  4. 时间复杂度:O(n),遍历数组一次。
  5. 空间复杂度:O(1),无额外空间开销。

步骤4:通过解决这个问题获得的启发

  1. 算法设计的重要性:摩尔投票法以 O(n) 的时间和 O(1) 的空间高效解决了问题,体现了精妙的算法设计对效率的提升。
  2. 多数性质的利用:当一个元素出现次数超过数组长度的一半时,不需要完全统计,利用其多数性质即可快速筛选。
  3. 扩展应用:摩尔投票法不仅适用于确定多数元素,还可扩展到寻找多于 n/3 次出现的元素(需要两轮计数)。

步骤5:实际应用分析

实际场景:
  1. 舆情分析

    • 在一个讨论群中,找出被提及最多的关键词。例如,在一个由用户输入的评论数据中,快速筛选出出现频率超过一半的品牌名称或产品关键词。
    • 实现方法
      • 将评论数据转化为数组形式,使用摩尔投票法筛选出最多的品牌关键词。
  2. 传感器数据监测

    • 在实时监测数据中,找出传感器的主流输出值,用于检测异常值。例如,某个值的输出频率异常高,可能表示系统进入了稳定状态。
  3. 选举系统

    • 在电子投票中,快速统计获胜的候选人(多数原则)。
实现示例:

在一个评论数据分析系统中,利用哈希表结合摩尔投票法,可以在多个评论字段中高效找出讨论最多的关键词。配合数据库或大数据平台,还可以实时生成分析报告,提升业务决策效率。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/483576.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

03-13、SpringCloud Alibaba第十三章,升级篇,服务降级、熔断和限流Sentinel

SpringCloud Alibaba第十三章&#xff0c;升级篇&#xff0c;服务降级、熔断和限流Sentinel 一、Sentinel概述 1、Sentinel是什么 随着微服务的流行&#xff0c;服务和服务之间的稳定性变得越来越重要。Sentinel 以流量为切入点&#xff0c;从流量控制、熔断降级、系统负载保…

基于vite6+ vue3 + electron@33 实现的 局域网内互传文件的桌面软件

目录 项目介绍项目部分截图介绍下基础项目搭建先搭建一个vite 前端项目 再安装 electron 相关依赖依赖安装失败解决方案修改 vite配置文件和 ts 配置文件修改packjsonts相关配置项目结构介绍 项目介绍 前端 基于 vue3 ts windicss 后端 就是node 层 项目地址&#xff1a; h…

安装MySQL 5.7 亲测有效

前言&#xff1a;本文是笔者在安装MySQL5.7时根据另一位博主大大的安装教程基础上做了一些修改而成 首先在这里表示对博主大大的感谢 下面附博主大大地址 下面的步骤言简意赅 跟着做就不会出错 希望各位读者耐下心来 慢慢解决安装中出现的问题~MySQL 5.7 安装教程&#xff08;全…

CSS函数

目录 一、背景 二、函数的概念 1. var()函数 2、calc()函数 三、总结 一、背景 今天我们就来说一说&#xff0c;常用的两个css自定义属性&#xff0c;也称为css函数。本文中就成为css函数。先来看一下官方对其的定义。 自定义属性&#xff08;有时候也被称作CSS 变量或者级…

6.824/6.5840 Lab 1: MapReduce

宁静的夏天 天空中繁星点点 心里头有些思念 思念着你的脸 ——宁夏 完整代码见&#xff1a; https://github.com/SnowLegend-star/6.824 由于这个lab整体难度实在不小&#xff0c;故考虑再三还是决定留下代码仅供参考 6.824的强度早有耳闻&#xff0c;我终于也是到了挑战这座高…

MongoDB集群分片安装部署手册

文章目录 一、集群规划1.1 集群安装规划1.2 端口规划1.3 目录创建 二、mongodb安装&#xff08;三台均需要操作&#xff09;2.1 下载、解压2.2 配置环境变量 三、mongodb组件配置3.1 配置config server的副本集3.1.1 config配置文件3.1.2 config server启动3.1.3 初始化config …

一种多功能调试工具设计方案开源

一种多功能调试工具设计方案开源 设计初衷设计方案具体实现HUB芯片采用沁恒微CH339W。TF卡功能网口功能SPI功能IIC功能JTAG功能下行USB接口 安路FPGA烧录器功能Xilinx FPGA烧录器功能Jlink OB功能串口功能RS232串口RS485和RS422串口自适应接口 CAN功能烧录器功能 目前进度后续计…

三维测量与建模笔记 - 5.3 光束法平差(Bundle Adjustment)

此篇笔记尚未理解&#xff0c;先做笔记。 如上图&#xff0c;在不同位姿下对同一个物体采集到了一系列图像&#xff0c; 例子中有四张图片。物体上某点M&#xff0c;在四幅图像上都能找到其观测点。 上式中的f函数是对使用做投影得到的估计点位置。求解这个方程有几种方法&…

力扣hot100道【贪心算法后续解题方法心得】(三)

力扣hot100道【贪心算法后续解题方法心得】 十四、贪心算法关键解题思路1、买卖股票的最佳时机2、跳跃游戏3、跳跃游戏 | |4、划分字母区间 十五、动态规划什么是动态规划&#xff1f;关键解题思路和步骤1、打家劫舍2、01背包问题3、完全平方式4、零钱兑换5、单词拆分6、最长递…

ElasticSearch学习篇19_《检索技术核心20讲》搜推广系统设计思想

目录 主要是包含搜推广系统的基本模块简单介绍&#xff0c;另有一些流程、设计思想的分析。 搜索引擎 基本模块检索流程 查询分析查询纠错 广告引擎 基于标签倒排索引召回基于向量ANN检索召回打分机制&#xff1a;非精确打分精准深度学习模型打分索引精简&#xff1a;必要的…

Ambrus 游戏工作室将应对气候变暖与游戏变现完美结合

当 Ambrus Studio 创始人兼 CEO Johnson Yeh 计划打造他称之为“第一款伟大的 Web3 游戏”时&#xff0c;他设立了两个关键目标&#xff1a;游戏需要在传统大型工作室忽视的市场中盈利&#xff0c;以及它需要具备超越娱乐的意义。 在 Sui 的帮助下&#xff0c;Johnson 和他的团…

KAN-Transfomer——基于新型神经网络KAN的时间序列预测

1.数据集介绍 ETT(电变压器温度)&#xff1a;由两个小时级数据集&#xff08;ETTh&#xff09;和两个 15 分钟级数据集&#xff08;ETTm&#xff09;组成。它们中的每一个都包含 2016 年 7 月至 2018 年 7 月的七种石油和电力变压器的负载特征。 traffic(交通) &#xff1a;描…

UEFI Spec 学习笔记---3 - Boot Manager(3)

3.2 Boot Manager Policy Protocol EFI_BOOT_MANAGER_POLICY_PROTOCOL----EFI应用程序使用该协议请求UEFI引导管理器使用平台策略连接设备。 typedef struct _EFI_BOOT_MANAGER_POLICY_PROTOCOL EFI_BOOT_MANAGER_POLICY_PROTOCOL; struct _EFI_BOOT_MANAGER_POLICY_PROTOCOL…

wordpress网站首页底部栏显示网站备案信息

一、页脚文件footer.php 例如&#xff0c;wordpress主题使用的是simple-life主题&#xff0c;服务器IP为192.168.68.89,在wordpress主题文件中有个页脚文件footer.php&#xff0c;这是一个包含网站页脚代码的文件。 footer.php 路径如下&#xff1a; /www/wwwroot/192.168.68…

QT实战-qt各种菜单样式实现

本文主要介绍了qt普通菜单样式、带选中样式、带子菜单样式、超过一屏幕菜单样式、自定义带有滚动条的菜单样式&#xff0c; 先上图如下&#xff1a; 1.普通菜单样式 代码&#xff1a; m_pmenu new QMenu(this);m_pmenu->setObjectName("quoteListMenu"); qss文…

数据结构实训——查找

声明&#xff1a; 以下是我们学校在学习数据结构时进行的实训&#xff0c;如涉及侵权马上删除文章 声明&#xff1a;本文主要用作技术分享&#xff0c;所有内容仅供参考。任何使用或依赖于本文信息所造成的法律后果均与本人无关。请读者自行判断风险&#xff0c;并遵循相关法…

指针(上)

目录 内存和地址 指针变量和地址 取地址&#xff08;&&#xff09; 解引用&#xff08;*&#xff09; 大小 类型 意义 const修饰 修饰变量 修饰指针 指针运算 指针- 整数 指针-指针 指针的关系运算 野指针 概念 成因 避免 assert断言 指针的使用 strl…

13TB的StarRocks大数据库迁移过程

公司有一套StarRocks的大数据库在大股东的腾讯云环境中&#xff0c;通过腾讯云的对等连接打通&#xff0c;通过dolphinscheduler调度datax离线抽取数据和SQL计算汇总&#xff0c;还有在大股东的特有的Flink集群环境&#xff0c;该环境开发了flink开发程序包部署&#xff0c;实时…

ARP表、MAC表、路由表的区别和各自作用

文章目录 ARP表、MAC表、路由表的区别和各自作用同一网络内:ARP表request - 请求reply - 响应 MAC地址在同一网络内,交换机如何工作? 不同网络路由表不同网络通信流程PC1到路由器路由器到PC2流程图 简短总结 ARP表、MAC表、路由表的区别和各自作用 拓扑图如下: 同一网络内:…

第七课 Unity编辑器创建的资源优化_UI篇(UGUI)

上期我们学习了简单的Scene优化&#xff0c;接下来我们继续编辑器创建资源的UGUI优化 UI篇&#xff08;UGUI&#xff09; 优化UGUI应从哪些方面入手&#xff1f; 可以从CPU和GPU两方面考虑&#xff0c;CPU方面&#xff0c;避免触发或减少Canvas的Rebuild和Rebatch&#xff0c…