当前位置: 首页 > news >正文

王道p18 第12题假设 A中的 n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出A的主元素。若存在主元素,则输出该元素:否则输出-1

 视频讲解在:👇

p18 第12题 c语言实现王道数据结构课后习题_哔哩哔哩_bilibili

从前向后扫描数组元素,标记出一个可能成为主元素的元素 Num。然后重新计数,确认 Num 是否是主元素。

我们可分为以下两步:
1.选取候选的主元素。依次扫描所给数组中的每个整数,将第一个遇到的整数 Num 保存到c中,记录 Num 的出现次数为 1:若遇到的下一个整数仍等于 Num,则计数加 ,否则计数减 1;当计数减到 0时,将遇到的下一个整数保存到c 中,计数重新记为 1,开始新一轮计数,即从当前位置开始重复上述过程,直到扫描完全部数组元素。

2.判断 c中元素是否是真正的主元素。再次扫描该数组,统计 c 中元素出现的次数,若大于n/2,则为主元素;否则,序列中不存在主元素。

让我们来看一下代码该如何实现

int majority(int a[], int n)
{int i = 0;int c = 0;//c用来保存候选主元素,count用来计数int count = 1;c = a[0];//设置a[0]为候选主元素for (i = 1; i < n; i++)//查找候选主元素{if (a[i] == c)//对a中的候选主元素计数count++;elseif (count > 0)//处理不是候选主元素的情况count--;else//更换候选主元素,重新计数{c = a[i];count = 1;}}if(count>0)//统计候选主元素的实际出现次数for (i = 0, count = 0; i < n; i++){if (a[i] == c)count++;}if (count > n / 2)//确认候选主元素return c;else//不存在主元素return -1;
}

完整测试代码

#include<stdio.h>
int a[8] = { 0,5,5,3,5,7,5,5};
int n = 8;
int majority(int a[], int n)
{int i = 0;int c = 0;//c用来保存候选主元素,count用来计数int count = 1;c = a[0];//设置a[0]为候选主元素for (i = 1; i < n; i++)//查找候选主元素{if (a[i] == c)//对a中的候选主元素计数count++;elseif (count > 0)//处理不是候选主元素的情况count--;else//更换候选主元素,重新计数{c = a[i];count = 1;}}if(count>0)//统计候选主元素的实际出现次数for (i = 0, count = 0; i < n; i++){if (a[i] == c)count++;}if (count > n / 2)//确认候选主元素return c;else//不存在主元素return -1;
}
int main()
{int ret = majority(a, n);if (ret != -1)printf("中位数为%d", ret);elseprintf("未找到");return 0;
}

用a[8]={0,5,5,3,5,1,5,7 }测试结果为

用a[8] = { 0,5,5,3,5,7,5,5}测试结果为

相关文章:

王道p18 第12题假设 A中的 n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出A的主元素。若存在主元素,则输出该元素:否则输出-1

视频讲解在&#xff1a;&#x1f447; p18 第12题 c语言实现王道数据结构课后习题_哔哩哔哩_bilibili 从前向后扫描数组元素&#xff0c;标记出一个可能成为主元素的元素 Num。然后重新计数&#xff0c;确认 Num 是否是主元素。 我们可分为以下两步: 1.选取候选的主元素。依…...

OpenTiny Vue 3.11.0 发布:增加富文本、ColorPicker等4个新组件,迎来了贡献者大爆发!

非常高兴跟大家宣布&#xff0c;2023年10月24日&#xff0c;OpenTiny Vue 发布了 v3.11.0 &#x1f389;。 OpenTiny 每次大版本发布&#xff0c;都会给大家带来一些实用的新特性&#xff0c;8.14 我们发布了 v3.10.0 版本&#xff0c;增加了4个新组件&#xff0c;组件 Demo 支…...

vivado查看报告和消息5

1、可配置报告策略 “ Configurable Report Strategies ” &#xff08; 可配置报告策略 &#xff09; 支持在 Vivado 工程模式下运行综合与实现的每个步骤之后选择 要运行的报告命令。根据设计阶段、设计复杂性和用户首选项&#xff0c; 需自动生成一组不同的报告以供频繁查…...

基于javaweb+mysql的jsp+servlet学生成绩管理系统(管理员、教师、学生)

博主24h在线&#xff0c;想要源码文档部署视频直接私聊&#xff0c;9.9元拿走&#xff01; 基于javawebmysql的jspservlet学生成绩管理系统(管理员、教师、学生)(javajspservletjavabeanmysqltomcat) 运行环境 Java≥8、MySQL≥5.7、Tomcat≥8 开发工具 eclipse/idea/myecl…...

基于卷积优化算法的无人机航迹规划-附代码

基于卷积优化算法的无人机航迹规划 文章目录 基于卷积优化算法的无人机航迹规划1.卷积优化搜索算法2.无人机飞行环境建模3.无人机航迹规划建模4.实验结果4.1地图创建4.2 航迹规划 5.参考文献6.Matlab代码 摘要&#xff1a;本文主要介绍利用卷积优化算法来优化无人机航迹规划。 …...

科技云报道:不卷自研大模型,金山办公如何创新生成式AI?

科技云报道原创。 过去大半年里&#xff0c;很多人对大模型的前景寄予厚望。主流观点认为&#xff0c;每个行业、每款产品都可以通过大模型“重做一遍”。 “重做一遍”听起来想象空间很大&#xff0c;但实际上多数大模型产品需要漫长的训练周期和海量资源投入&#xff0c;落…...

3BHE022291R0101 PCD230A 专注于制造卓越人工智能

3BHE022291R0101 PCD230A 专注于制造卓越人工智能 BISTelligence是BISTel的一个分支&#xff0c;BISTel是为全球半导体和FPD制造商提供工程和软件自动化产品的领先供应商。半导体产品集团上个月被卖给了新思科技。在出售给Synopsys之后&#xff0c;Bisetlliegnce成立了两个部门…...

小程序 scroll-view 性能问题

先说使用场景&#xff0c;一次加载很多数据造成小程序卡顿的问题 &#xff0c;找了好多都没有好的解决办法&#xff0c;要么太过复杂&#xff0c;然后研究了两天通过简单的办法实现&#xff0c;先根据数量把高度撑开&#xff0c;然后根据滚动位置渲染指定的数据就可以了&#x…...

【移远QuecPython】EC800M物联网开发板的硬件PWM和PWM输出BUG

【移远QuecPython】EC800M物联网开发板的硬件PWM和PWM输出BUG 文章目录 导入库初始化PWM开启PWMPWM硬件BUG硬件BUG复现原因附录&#xff1a;列表的赋值类型和py打包列表赋值BUG复现代码改进优化总结 py打包 导入库 from misc import PWM_V2或者 from misc import PWM但我觉得…...

OverDraw的优化

在uwa搜寻到的一些overDraw优化方法 透明图片避免绘制来减少overDraw 像一些alpha0的图片&#xff0c;根本没有必要参与绘制。所以留一些可以参与Raycast&#xff0c;但是不绘制 using UnityEngine; using System.Collections;namespace UnityEngine.UI {public class Empty…...

数据结构—字符串

文章目录 7.字符串(1).字符串及其ADT#1.基本概念#2.ADT (2).字符串的基本操作#1.求子串substr#2.插入字符串insert#3.其他操作 (3).字符串的模式匹配#1.简单匹配(Brute-Force方法)#2.KMP算法I.kmp_match()II.getNext() #3.还有更多 小结附录&#xff1a;我自己写的string 7.字符…...

inne所属公司抢注“童年时光”商标仍被冻结

根据中国商标网查询&#xff0c;国家知识产权局已于2023年3月10日裁定&#xff0c;被告inne所属的南京童年时光生物技术有限公司注册的“童年时光”商标无效。随着这起保健品行业品牌资产争夺事件的发酵&#xff0c;更多的细节得到披露&#xff0c;至此&#xff0c;一个从“代理…...

20231106-前端学习加载和视频球特效

加载效果 代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>加载效果</title><!-- 最新…...

Arrays.asList() 和 List.of() 的列表之争

1. 概述 有时在Java中&#xff0c;为了方便&#xff0c;我们需要创建一个小列表或将数组转换为列表。Java 为此提供了一些辅助方法。 在本文中&#xff0c;我们将比较初始化小型临时数组的两种主要方法&#xff1a;List.of()和 Array.asList()。 2. Arrays.asList() Java 自…...

基于51单片机的停车场管理系统仿真电路设计

**单片机设计介绍&#xff0c;基于51单片机的停车场管理系统仿真电路设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 停车场管理系统仿真电路设计介绍 停车场管理系统主要用于自动化管理和控制停车场&#xff0c;以提高停车…...

APIView单一资源的查看更新删除

APIView单一资源的查看更新删除 一、构建路由 re_path("author/(/d)",AuthorDetailView.as_view)), 二、视图类 在views.py中添加AuthorDetailView类 class AuthorDetailView(APIView):def get(self, request, pk):author Author.objects.get(pkpk)serializer A…...

UML--类图的表示

1. 类的表示 1.1 访问属性 : public -: private #: protected 1.2 接口与抽象类 斜体 表示抽象类和抽象方法 <<Interface>> 类表示接口 1.3 类图示意 Mclass- val: int getVal(): int 2. 类关系 2.1 实现关系 空心三角形和虚线组成 B实现A,则三角形尖尖朝…...

JVM字节码文件浅谈

文章目录 版权声明java虚拟机的组成字节码文件打开字节码文件的姿势字节码文件的组成魔数&#xff08;基本信息&#xff09;主副版本号&#xff08;基本信息&#xff09;主版本号不兼容的错误解决方法基本信息常量池方法 字节码文件的常用工具javap -v命令jclasslib插件阿里art…...

DBever 连接trino时区问题 The datetime zone id ‘GMT+08:00‘ is not recognised

DBever连接trino 测试连接成功&#xff0c;但是执行sql报时区不对、如果你默认使用的是大于jdk8的版本 会存在这个问题&#xff0c;因为jdk版本 jdk8 和jdk17 版本默认时区是不同的 trino官网明确说明了时区默认跟jdk走 解决方案 可以先行查看JDK本地时区库版本&#xff0c;执…...

xlua源码分析(二)lua Call C#的无wrap实现

xlua源码分析&#xff08;二&#xff09;lua Call C#的无wrap实现 上一节我们主要分析了xlua中C# Call lua的实现思路&#xff0c;本节我们将根据Examples 03_UIEvent&#xff0c;分析lua Call C#的底层实现。例子场景里有一个简单的UI面板&#xff0c;面板中包含一个input fie…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...

文件上传漏洞防御全攻略

要全面防范文件上传漏洞&#xff0c;需构建多层防御体系&#xff0c;结合技术验证、存储隔离与权限控制&#xff1a; &#x1f512; 一、基础防护层 前端校验&#xff08;仅辅助&#xff09; 通过JavaScript限制文件后缀名&#xff08;白名单&#xff09;和大小&#xff0c;提…...