王道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
视频讲解在:👇 p18 第12题 c语言实现王道数据结构课后习题_哔哩哔哩_bilibili 从前向后扫描数组元素,标记出一个可能成为主元素的元素 Num。然后重新计数,确认 Num 是否是主元素。 我们可分为以下两步: 1.选取候选的主元素。依…...
OpenTiny Vue 3.11.0 发布:增加富文本、ColorPicker等4个新组件,迎来了贡献者大爆发!
非常高兴跟大家宣布,2023年10月24日,OpenTiny Vue 发布了 v3.11.0 🎉。 OpenTiny 每次大版本发布,都会给大家带来一些实用的新特性,8.14 我们发布了 v3.10.0 版本,增加了4个新组件,组件 Demo 支…...
vivado查看报告和消息5
1、可配置报告策略 “ Configurable Report Strategies ” ( 可配置报告策略 ) 支持在 Vivado 工程模式下运行综合与实现的每个步骤之后选择 要运行的报告命令。根据设计阶段、设计复杂性和用户首选项, 需自动生成一组不同的报告以供频繁查…...
基于javaweb+mysql的jsp+servlet学生成绩管理系统(管理员、教师、学生)
博主24h在线,想要源码文档部署视频直接私聊,9.9元拿走! 基于javawebmysql的jspservlet学生成绩管理系统(管理员、教师、学生)(javajspservletjavabeanmysqltomcat) 运行环境 Java≥8、MySQL≥5.7、Tomcat≥8 开发工具 eclipse/idea/myecl…...
基于卷积优化算法的无人机航迹规划-附代码
基于卷积优化算法的无人机航迹规划 文章目录 基于卷积优化算法的无人机航迹规划1.卷积优化搜索算法2.无人机飞行环境建模3.无人机航迹规划建模4.实验结果4.1地图创建4.2 航迹规划 5.参考文献6.Matlab代码 摘要:本文主要介绍利用卷积优化算法来优化无人机航迹规划。 …...
科技云报道:不卷自研大模型,金山办公如何创新生成式AI?
科技云报道原创。 过去大半年里,很多人对大模型的前景寄予厚望。主流观点认为,每个行业、每款产品都可以通过大模型“重做一遍”。 “重做一遍”听起来想象空间很大,但实际上多数大模型产品需要漫长的训练周期和海量资源投入,落…...
3BHE022291R0101 PCD230A 专注于制造卓越人工智能
3BHE022291R0101 PCD230A 专注于制造卓越人工智能 BISTelligence是BISTel的一个分支,BISTel是为全球半导体和FPD制造商提供工程和软件自动化产品的领先供应商。半导体产品集团上个月被卖给了新思科技。在出售给Synopsys之后,Bisetlliegnce成立了两个部门…...
小程序 scroll-view 性能问题
先说使用场景,一次加载很多数据造成小程序卡顿的问题 ,找了好多都没有好的解决办法,要么太过复杂,然后研究了两天通过简单的办法实现,先根据数量把高度撑开,然后根据滚动位置渲染指定的数据就可以了&#x…...
【移远QuecPython】EC800M物联网开发板的硬件PWM和PWM输出BUG
【移远QuecPython】EC800M物联网开发板的硬件PWM和PWM输出BUG 文章目录 导入库初始化PWM开启PWMPWM硬件BUG硬件BUG复现原因附录:列表的赋值类型和py打包列表赋值BUG复现代码改进优化总结 py打包 导入库 from misc import PWM_V2或者 from misc import PWM但我觉得…...
OverDraw的优化
在uwa搜寻到的一些overDraw优化方法 透明图片避免绘制来减少overDraw 像一些alpha0的图片,根本没有必要参与绘制。所以留一些可以参与Raycast,但是不绘制 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.还有更多 小结附录:我自己写的string 7.字符…...
inne所属公司抢注“童年时光”商标仍被冻结
根据中国商标网查询,国家知识产权局已于2023年3月10日裁定,被告inne所属的南京童年时光生物技术有限公司注册的“童年时光”商标无效。随着这起保健品行业品牌资产争夺事件的发酵,更多的细节得到披露,至此,一个从“代理…...
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中,为了方便,我们需要创建一个小列表或将数组转换为列表。Java 为此提供了一些辅助方法。 在本文中,我们将比较初始化小型临时数组的两种主要方法:List.of()和 Array.asList()。 2. Arrays.asList() Java 自…...
基于51单片机的停车场管理系统仿真电路设计
**单片机设计介绍,基于51单片机的停车场管理系统仿真电路设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 停车场管理系统仿真电路设计介绍 停车场管理系统主要用于自动化管理和控制停车场,以提高停车…...
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虚拟机的组成字节码文件打开字节码文件的姿势字节码文件的组成魔数(基本信息)主副版本号(基本信息)主版本号不兼容的错误解决方法基本信息常量池方法 字节码文件的常用工具javap -v命令jclasslib插件阿里art…...
DBever 连接trino时区问题 The datetime zone id ‘GMT+08:00‘ is not recognised
DBever连接trino 测试连接成功,但是执行sql报时区不对、如果你默认使用的是大于jdk8的版本 会存在这个问题,因为jdk版本 jdk8 和jdk17 版本默认时区是不同的 trino官网明确说明了时区默认跟jdk走 解决方案 可以先行查看JDK本地时区库版本,执…...
xlua源码分析(二)lua Call C#的无wrap实现
xlua源码分析(二)lua Call C#的无wrap实现 上一节我们主要分析了xlua中C# Call lua的实现思路,本节我们将根据Examples 03_UIEvent,分析lua Call C#的底层实现。例子场景里有一个简单的UI面板,面板中包含一个input fie…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
