当前位置: 首页 > 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. 延后初始化 (原书第…...

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

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

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...

C++实现分布式网络通信框架RPC(2)——rpc发布端

有了上篇文章的项目的基本知识的了解&#xff0c;现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...