【C语言】每日一题(多数元素)

多数元素,链接奉上

方法

  • 1.摩尔投票
  • 2.合理但错误的方法
    • 2.1暴力循环
    • 2.2排序+求出中间元素中间元素

在这里插入图片描述

1.摩尔投票

先来简单的介绍摩尔投票:

摩尔投票是一种用来解决绝对众数问题的算法。

什么是绝对众数呢?

在一个集合中,如果一个元素的出现次数比其他所有元素的出现次数之和还多,那么就称它为这个集合的绝对众数。等价地说,绝对众数的出现次数大于总元素数的一半。

思路:

设置一个计数器count
利用绝对众数与非绝对众数相互对抗、抵消,
首先遍历数组
遇到相同的count++,不同的count--
在根据count的数值设置当前的candidate(投票对象)
因为绝对众数>非绝对众数,对抗过后剩下的那个元素一定是绝对众数

代码实现:

int majorityElement(int* nums, int numsSize)
{//mooreint i=0;int candidate=nums[0];//设置投票对象int count=1;//因为投票对象是nums[0],本身就是1票for(i=1,count=1;i<numsSize;i++)//遍历数组{if(candidate==nums[i])//当投票对象与当前元素相同时count++count++;else{//否则count--count--;if(count<0)//当投票对象票数<0,重新选择对象{candidate=nums[i];count=1;//票数重置为1}}}return candidate;
}

2.合理但错误的方法

这是题主自己经历的错误,因为超出运行时间,所以不可以用

但是
注意2.2中的方法会根据排序的不同方法而产生不同影响
例如:

冒泡排序会时间出界,但快速排序不会

2.1暴力循环

马有失蹄,暴力循环也会

思路:

设置计数器count=0
利用外部循环变量作为数组下标,
在内层也设置一个循环变量为数组下标,
与每一个数组元素进行比较,相同时count++ 当满足count>numssize/2break

代码实现:

int majorityElement(int* nums, int numsSize)
{int i = 0;for (i = 0; i < numsSize; i++){int count = 0;for (int j = 0; j < numsSize; j++){if (nums[i] == nums[j])count++;}if (count > numsSize / 2)break;}return nums[i];}

2.2排序+求出中间元素中间元素

思路:

先进行排序,之后求出nums[numsSize/2](中间元素),因为绝对众数所占元素必定过半,故中间元素一定为绝对众数,再return中间元素

代码实现:

int majorityElement(int* nums, int numsSize)
{int i = 0;int tmp = 0;for (i = 0; i < numsSize - 1; i++){for (int j = 0; j < numsSize - 1 - i; j++){if (nums[j] > nums[j + 1]){tmp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = tmp;}}}return nums[numsSize/2];
}

欢迎讨论哦

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

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

相关文章

PHP最简单自定义自己的框架model使用(七)

1、实现model使用效果 2、自动加载model,KJ.php //自动加载文件public static function _autoload($className){switch ($className){//自动model类case substr($className,-5)Model:$path MODEL./.$className..php;if(is_file($path)) include $path;break;//自动加载控制器…

机器学习理论笔记(一):初识机器学习

文章目录 1 前言&#xff1a;蓝色是天的机器学习笔记专栏1.1 专栏初衷与定位1.2 本文主要内容 2 机器学习的定义2.1 机器学习的本质2.2 机器学习的分类 3 机器学习的基本术语4 探索"没有免费的午餐"定理&#xff08;NFL&#xff09;5 结语 1 前言&#xff1a;蓝色是天…

隧道人员定位方案

针对隧道环境的人员定位方案&#xff0c;UWB定位技术同样可以提供高精度和可靠的定位服务。以下是一个可行的方案&#xff1a; 部署基站网络&#xff1a;在隧道内建立一个基站网络&#xff0c;基站需要均匀分布在各个关键位置&#xff0c;以确保全方位的覆盖。由于隧道的特殊环…

一、Dubbo 简介与架构

一、Dubbo 简介与架构 1.1 应用架构演进过程 单体应用&#xff1a;JEE、MVC分布式应用&#xff1a;SOA、微服务化 1.2 Dubbo 简介一种分布式 RPC 框架&#xff0c;对专业知识&#xff08;序列化/反序列化、网络、多线程、设计模式、性能优化等&#xff09;进行了更高层的抽象和…

SpringBoot集成Redis及Redis使用方法

目录 应用背景 Redis简介 更新问题 一&#xff1a;环境配置 1.1: 在pom.xml文件中添加依赖 1.2&#xff1a;配置SpringBoot核心配置文件application.properties 二&#xff1a;在Config文件夹中创建RedisConfig配置文件类 2.1&#xff1a;RedisTemplate中的几个角色&am…

基于安防监控EasyCVR视频汇聚融合技术的运输管理系统的分析

一、项目背景 近年来&#xff0c;随着物流行业迅速发展&#xff0c;物流运输费用高、运输过程不透明、货损货差率高、供应链协同能力差等问题不断涌现&#xff0c;严重影响了物流作业效率&#xff0c;市场对于运输管理数字化需求愈发迫切。当前运输行业存在的难题如下&#xf…

mysql-事务特性以及隔离机制

一.ACID 事务&#xff08;Transaction&#xff09;是访问和更新数据库的程序执行单元&#xff1b;事务中可能包含一个或多个sql语句&#xff0c;这些语句要么都执行&#xff0c;要么都不执行。 1.逻辑架构和存储引擎 如上图所示&#xff0c;MySQL服务器逻辑架构从上往下可以分…

【密码学】维京密码

维京密码 瑞典罗特布鲁纳巨石上的图案看起来毫无意义&#xff0c;但是它确实是一种维京密码。如果我们注意到每组图案中长笔画和短笔画的数量&#xff0c;将得到一组数字2、4、2、3、3、5、2、3、3、6、3、5。组合配对得到24、23、35、23、36、35。现在考虑如图1.4所示的内容&a…

六、Linux系统下,文件操作命令都有哪些?

总括&#xff1a; 创建文件/文件夹&#xff1a;touch&#xff1b; 查看&#xff1a;cat/more&#xff1b; 复制&#xff1a;copy&#xff1b; 移动文件/文件夹&#xff1a;mv&#xff1b; 删除&#xff1a;rm&#xff1b; 1、创建文件 &#xff08;1&#xff09;语法&#x…

java实现docx,pdf文件动态填充数据

一&#xff0c;引入pom 根据需求引入自己所需pom org.apache.poi poi 4.1.1 org.apache.poi poi-ooxml 4.1.1 org.jxls jxls 2.6.0 ch.qos.logback logback-core org.jxls jxls-poi 1.2.0 fr.opensagres.xdocreport fr.opensagres.xdocreport.core 2.0.2 fr.opensagres.xdocrep…

最小生成树 — Prim算法

同Kruskal算法一样&#xff0c;Prim算法也是最小生成树的算法&#xff0c;但与Kruskal算法有较大的差别。 Prim算法整体是通过“解锁” “选中”的方式&#xff0c;点 -> 边 -> 点 -> 边。 因为是最小生成树&#xff0c;所以针对的也是无向图&#xff0c;所以可以随意…

MySql011——检索数据:过滤数据(使用正则表达式)

前提&#xff1a;使用《MySql006——检索数据&#xff1a;基础select语句》中创建的products表 一、正则表达式介绍 关于正则表达式的介绍大家可以看我的这一篇博客《Java038——正则表达式》&#xff0c;这里就不再累赘。 二、使用MySQL正则表达式 2.1、基本字符匹配 检索…

Java版企业电子招投标采购系统源码之首页设计 tbms

​ 功能描述 1、门户管理&#xff1a;所有用户可在门户页面查看所有的公告信息及相关的通知信息。主要板块包含&#xff1a;招标公告、非招标公告、系统通知、政策法规。 2、立项管理&#xff1a;企业用户可对需要采购的项目进行立项申请&#xff0c;并提交审批&#xff0c;查…

照耀国产的星火,再度上新!

国产之光&#xff0c;星火闪耀 ⭐ 新时代的星火⭐ 多模态能力⭐ 图像生成与虚拟人视频生成⭐ 音频生成与OCR笔记收藏⭐ 助手模式更新⭐ 插件能力⭐ 代码能力⭐ 写在最后 ⭐ 新时代的星火 在这个快速变革的时代&#xff0c;人工智能正迅猛地催生着前所未有的革命。从医疗到金融…

CEC2013(MATLAB):遗传算法(Genetic Algorithm,GA)求解CEC2013的28个函数

一、遗传算法GA 遗传算法&#xff08;Genetic Algorithm&#xff0c;GA&#xff09;起源于对生物系统所进行的计算机模拟研究&#xff0c;是一种随机全局搜索优化方法&#xff0c;它模拟了自然选择和遗传中发生的复制、交叉(crossover)和变异(mutation)等现象&#xff0c;从任…

easyx图形库基础4:贪吃蛇

贪吃蛇 一实现贪吃蛇&#xff1a;1.绘制网格&#xff1a;1.绘制蛇&#xff1a;3.控制蛇的默认移动向右&#xff1a;4.控制蛇的移动方向&#xff1a;5.生成食物6.判断蛇吃到食物并且长大。7.判断游戏结束&#xff1a;8.重置函数&#xff1a; 二整体代码&#xff1a; 一实现贪吃蛇…

【0基础学爬虫】爬虫基础之网络请求库的使用

大数据时代&#xff0c;各行各业对数据采集的需求日益增多&#xff0c;网络爬虫的运用也更为广泛&#xff0c;越来越多的人开始学习网络爬虫这项技术&#xff0c;K哥爬虫此前已经推出不少爬虫进阶、逆向相关文章&#xff0c;为实现从易到难全方位覆盖&#xff0c;特设【0基础学…

安卓13解决链接问题

作为Android用户&#xff0c;你可能已经注意到了一个问题——Android 13不再支持PPTP协议。但请别担心&#xff0c;作为一家专业的代理供应商&#xff0c;我们将与你分享解决方案&#xff0c;让你轻松解决L2TP问题&#xff0c;享受到高水平的连接体验。本文将为你提供实用的操作…

什么是浮动(float)?如何清除浮动?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 浮动&#xff08;Float&#xff09;和清除浮动⭐ 浮动的使用⭐ 清除浮动1. 空元素法&#xff08;Empty Element Method&#xff09;2. 使用 Clearfix Hack3. 使用 Overflow ⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发…

微服务与Nacos概述-5

引入OpenFeign 添加依赖&#xff1a; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId> </dependency> <dependency><groupId>com.alibaba.cloud</groupId>…