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

【笔记】数据结构12

文章目录

  • 2013年408应用题41
      • 方法一
      • 方法二

看到的社区的一个知识总结,这里记录一下。
知识点汇总

2013年408应用题41

在这里插入图片描述
解决方法:

方法一

(1)算法思想

算法的策略是从前向后扫描数组元素,标记出一个可能成为主元素的元素Num。然后重新计数,确认Num是否是主元素。算法可分为以下两步:

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

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

(2)代码如下:

#include<stdio.h>
#include<stdlib.h>int Majority(int A[],int n){int i,c,count = 1;//c用来保存候选主元素,count用来计数c=A[0];//设置A[0]为候选主元素for(i=1;i<n;i++){if(A[i]==c)	count++;//对A中的候选主元素进行排序else if(count>0)count--;else {c=A[i];count=1;}}if(count>0){//判断c中元素是否是真正的主元素for(i=count=0;i<n;i++)if(A[i]==c)count++;}if(count>n/2)return c;else return -1;
}

该算法的时间复杂度为O(n),空间复杂度为O(1)。

(与算法一致且回答正确,时间空间各一分)

方法二

采用计数排序的思想

申请一个辅助计数数组,如果数字出现一次则在辅助技术数组中加一,返回查看辅助计数数组,如果出现次数大于n/2,则返回元素max,否则返回-1

#include<stdio.h>
#include<stdlib.h>int Majority(int A[],int n){int k,*p,max;p=(int *)malloc(sizeof(int)*n);//申请辅助计数数组for(k=0;k<n;k++){p[k]=0;}max=0;for(k=0;k<n;k++){p[A[k]]++;if(p[A[k]]>p[max])max=A[k];}if(p[max]>n/2)return max;else return -1;}

相关文章:

【笔记】数据结构12

文章目录 2013年408应用题41方法一方法二 看到的社区的一个知识总结&#xff0c;这里记录一下。 知识点汇总 2013年408应用题41 解决方法&#xff1a; 方法一 &#xff08;1&#xff09;算法思想 算法的策略是从前向后扫描数组元素&#xff0c;标记出一个可能成为主元素的元…...

django的URL配置

1 django如何处理一个请求 首先Django要使用根URLconf模块&#xff0c;通过setting.py配置文件的ROOT_URLCONF来设置。 加载该模块后并查找变量 urlpatterns。这是一个Python的django.conf.urls.url()实例列表。 Django按顺序运行每个URL模式&#xff0c;并在匹配所请求的…...

精华帖分享 | 因子构建思考1

本文来源于量化小论坛股票量化板块精华帖&#xff0c;作者为z-coffee。 以下为精华帖正文&#xff1a; 一段时间没写帖子&#xff0c;其实一直在研究策略&#xff0c;只是从不同的角度去思考而已。熟悉我的老板其实清楚&#xff0c;我的炉子水平一般&#xff0c;基本不太依托…...

kubernetes笔记(四)

一、Pod调度策略 1.基于节点的调度 spec->nodeName [rootmaster ~]# vim myhttp.yaml --- kind: Pod apiVersion: v1 metadata:name: myhttp spec:nodeName: node-0001 # 基于节点名称进行调度containers:- name: apacheimage: myos:httpd[rootmaster ~]# kubectl a…...

通信工程学习:什么是SNMP简单网络管理协议

SNMP&#xff1a;简单网络管理协议 SNMP&#xff08;Simple Network Management Protocol&#xff0c;简单网络管理协议&#xff09;是一种用于在计算机网络中管理网络节点&#xff08;如服务器、工作站、路由器、交换机等&#xff09;的标准协议。它属于OSI模型的应用层&#…...

ubuntu20.04系统下,c++图形库Matplot++配置

linux下安装c图形库Matplot&#xff0c;使得c可以可视化编程&#xff1b;安装Matplot之前&#xff0c;需要先安装一个gnuplot&#xff0c;因为Matplot是依赖于此库 gnuplot下载链接&#xff1a; http://www.gnuplot.info/ 一、gnuplot下载与安装(可以跳过&#xff0c;下面源码…...

[激光原理与应用-126]:南京科耐激光-激光焊接 - 焊中无损检测技术 - 智能制程监测系统IPM介绍 - 26- 频域分析法

目录 一、什么是频域分析法 1、定义 2、基本原理 3、分析步骤 4、应用领域 5、优缺点 二、频域分析法在激光焊接故障监测中的应用 2.1 概述 1、应用背景 2、频域分析法的应用 3、应用优势 4、应用实例 2.2 激光焊接故障检测中光电信号的频谱特征 1、光电信号分类…...

深入理解 Solidity 修饰符(Modifier):功能、应用与最佳实践

1. 什么是修饰符&#xff08;Modifier&#xff09;&#xff1f; 1.1 修饰符的定义 在 Solidity 中&#xff0c;修饰符&#xff08;Modifier&#xff09;是一种用于更改函数行为的关键字。它们可以用于控制函数的执行条件、添加前置检查、简化重复逻辑等。修饰符在函数执行之前…...

YOLO11项目实战1:道路缺陷检测系统设计【Python源码+数据集+运行演示】

一、项目背景 随着城市化进程的加速和交通网络的不断扩展&#xff0c;道路维护成为城市管理中的一个重要环节。道路缺陷&#xff08;如裂缝、坑洞、路面破损等&#xff09;不仅影响行车安全&#xff0c;还会增加车辆的磨损和维修成本。传统的道路缺陷检测方法主要依赖人工巡检…...

怎么屏蔽统计系统统计到的虚假ip

屏蔽统计系统中的虚假IP是保护网站分析数据准确性的重要措施。以下是一些有效的策略和步骤&#xff0c;可以帮助您过滤掉虚假IP&#xff1a; 1. 识别虚假IP的特征 了解虚假IP的常见特征可以帮助您识别和屏蔽它们&#xff1a; 短时间内高频率访问&#xff1a;虚假IP可能会在短…...

前端开发设计模式——策略模式

目录 一、策略模式的定义和特点 1.定义&#xff1a; 2.特点&#xff1a; 二、策略模式的实现方式 1.定义策略接口&#xff1a; 2.创建具体策略类&#xff1a; 3.定义上下文类&#xff1a; 三、策略模式的应用场景 1.表单验证场景&#xff1a; 2.动画效果切换场景&…...

SysML案例-潜艇

DDD领域驱动设计批评文集>> 《软件方法》强化自测题集>> 《软件方法》各章合集>>...

车辆重识别(2020NIPS去噪扩散概率模型)论文阅读2024/9/27

[2] Denoising Diffusion Probabilistic Models 作者&#xff1a;Jonathan Ho Ajay Jain Pieter Abbeel 单位&#xff1a;加州大学伯克利分校 摘要&#xff1a; 我们提出了高质量的图像合成结果使用扩散概率模型&#xff0c;一类潜变量模型从非平衡热力学的考虑启发。我们的最…...

基于深度学习的任务序列中的快速适应

基于深度学习的任务序列中的快速适应是指模型在接连处理不同任务时&#xff0c;能够迅速调整和优化自身以适应新任务的能力。这种能力在动态环境和多任务学习中尤为重要&#xff0c;旨在减少训练时间和资源需求。以下是这一主题的关键要素&#xff1a; 1. 快速适应的背景 动态…...

虚拟机三种网络模式详解

在电脑里开一台虚拟机&#xff0c;是再常见不过的操作了。无论是用虚拟机玩只有旧版本系统能运行的游戏&#xff0c;还是用来学习Linux、跑跑应用程序都是很好的。而这其中&#xff0c;虚拟机网络是绝对绕不过去的。本篇文章通俗易懂的介绍了常见的虚拟网络提供的三种网络链接模…...

[leetcode]674_最长连续递增序列

给定一个未经排序的整数数组&#xff0c;找到最长且 连续递增的子序列&#xff0c;并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r&#xff08;l < r&#xff09;确定&#xff0c;如果对于每个 l < i < r&#xff0c;都有 nums[i] < nums[i 1] &am…...

【无人机设计与技术】四旋翼无人机,UAV仿真,轨迹跟踪PID控制

摘要 本文探讨了四旋翼无人机&#xff08;UAV&#xff09;在轨迹跟踪中的PID控制仿真方法。通过设计三轴方向的PID控制器&#xff0c;调节无人机的姿态与位置&#xff0c;使其能够准确跟踪预设轨迹。本文使用MATLAB/Simulink进行了建模与仿真&#xff0c;验证了PID控制算法在无…...

回归预测|基于卷积神经网络-支持向量机的数据回归预测Matlab程序CNN-SVM 卷积提取特征与原始特征进行融合预测

回归预测|基于卷积神经网络-支持向量机的数据回归预测Matlab程序CNN-SVM 卷积提取特征与原始特征进行融合预测 文章目录 一、基本原理原理流程总结 二、实验结果三、核心代码四、代码获取五、总结 回归预测|基于卷积神经网络-支持向量机的数据回归预测Matlab程序CNN-SVM 卷积提…...

javaScript基础知识汇总

一、基础语法 1、区分大小写&#xff1a;无论是变量、函数名还是操作符&#xff0c;都区分大小写。 2、标识符&#xff1a;就是变量、函数、属性或函数参数的名称。标识符可以由一个或多个字符构成&#xff0c;但需要满足以下条件&#xff1a; 第一个字符必须是一个字母、下…...

《动手学深度学习》笔记2.2——神经网络从基础→进阶 (参数管理-每层的权重/偏置)

目录 0. 前言 正文&#xff1a;参数管理 1. 参数访问 1.1 [目标参数] 1.2 [一次性访问所有参数] 1.3 [从嵌套块收集参数] 2. 参数初始化 2.1 [内置初始化] 2.2 [自定义初始化] 2.3 [参数绑定-共享参数] 3. 小结&#xff08;第2节&#xff09; 4. 延后初始化 (原书第…...

OpenClaw+Qwen3-VL:30B:个人多模态AI助手全流程

OpenClawQwen3-VL:30B&#xff1a;个人多模态AI助手全流程 1. 为什么选择这个组合&#xff1f; 去年冬天&#xff0c;我发现自己陷入了一个典型的知识工作者困境&#xff1a;每天要处理大量图片资料&#xff08;产品截图、会议白板照片、技术文档截图&#xff09;&#xff0c…...

PostgreSQL权限管理实操:Homebrew安装后,如何正确创建postgres用户并导入项目数据

PostgreSQL权限管理实战&#xff1a;从Homebrew安装到项目数据迁移全指南 当你用Homebrew完成PostgreSQL安装后&#xff0c;真正的挑战才刚刚开始。许多开发者卡在权限配置这一关&#xff0c;导致后续数据迁移和日常操作频频受阻。本文将带你深入PostgreSQL的权限体系&#xff…...

将Autoresearch转化为通用技能

我是一名技术作家。我每天在文档仓库、Markdown 文件、API 参考、风格指南和 SEO 审计中度过。我不训练语言模型。我不写 CUDA 内核。但当 Andrej Karpathy 发布了他的 autoresearch 时&#xff0c;我无法停止思考它。 这个想法太简单了&#xff0c;事后看来似乎很明显&#x…...

mmsegmentation训练策略调优全攻略:从学习率预热到迭代次数计算

mmsegmentation训练策略调优实战&#xff1a;从参数配置到显存优化 在图像分割领域&#xff0c;mmsegmentation框架因其模块化设计和丰富的预训练模型而广受欢迎。但真正决定模型性能上限的&#xff0c;往往是那些容易被忽视的训练策略细节。本文将带您深入AdamW优化器的参数微…...

Fast-GitHub:突破网络瓶颈的开发效率工具解决方案

Fast-GitHub&#xff1a;突破网络瓶颈的开发效率工具解决方案 【免费下载链接】Fast-GitHub 国内Github下载很慢&#xff0c;用上了这个插件后&#xff0c;下载速度嗖嗖嗖的~&#xff01; 项目地址: https://gitcode.com/gh_mirrors/fa/Fast-GitHub 1 痛点直击&#xff…...

PHP 的异步编程 该怎么选择

一切的起点&#xff1a;synchronized 的舒适区 刚开始写代码时&#xff0c;思维往往停留在"单机"模式。遇到需要控制并发的地方&#xff0c;直觉反应就是加个 synchronized 关键字。 1. 曾经写过的代码 // 简单的库存扣减 public synchronized void deductStock(Stri…...

C++的std--ranges算法自定义比较器与等价关系在集合操作中的运用

C20引入的std::ranges库为算法操作带来了革命性改进&#xff0c;其中自定义比较器与等价关系的灵活运用&#xff0c;显著提升了集合操作的表达能力。通过精确控制元素间的比较逻辑&#xff0c;开发者能够实现更复杂的业务需求&#xff0c;例如处理自定义对象集合或实现非标准排…...

使用AI大大提升了学习代码的效率

最近看到一个观点&#xff0c;说AI的发展导致代码越来越不值钱了&#xff0c;AI降低了我们学习的门槛&#xff0c;大大提升了学习效率。好像很多程序都可以一个人一天上架一款产品。或许有夸张成分&#xff0c;但像我们普通人都体验到了AI的方便&#xff0c;比如在项目开发的过…...

AI药物研发加速发现:DeepChem深度学习框架实战指南

AI药物研发加速发现&#xff1a;DeepChem深度学习框架实战指南 【免费下载链接】deepchem Democratizing Deep-Learning for Drug Discovery, Quantum Chemistry, Materials Science and Biology 项目地址: https://gitcode.com/GitHub_Trending/de/deepchem 深度学习药…...

突破VMware限制:在非苹果硬件上构建macOS开发环境完全指南

突破VMware限制&#xff1a;在非苹果硬件上构建macOS开发环境完全指南 【免费下载链接】unlocker 项目地址: https://gitcode.com/gh_mirrors/unloc/unlocker 实现跨平台macOS体验&#xff1a;VMware Unlocker核心价值解析 当开发者需要在Windows或Linux工作站上构建m…...