【笔记】数据结构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方法一方法二 看到的社区的一个知识总结,这里记录一下。 知识点汇总 2013年408应用题41 解决方法: 方法一 (1)算法思想 算法的策略是从前向后扫描数组元素,标记出一个可能成为主元素的元…...
django的URL配置
1 django如何处理一个请求 首先Django要使用根URLconf模块,通过setting.py配置文件的ROOT_URLCONF来设置。 加载该模块后并查找变量 urlpatterns。这是一个Python的django.conf.urls.url()实例列表。 Django按顺序运行每个URL模式,并在匹配所请求的…...
精华帖分享 | 因子构建思考1
本文来源于量化小论坛股票量化板块精华帖,作者为z-coffee。 以下为精华帖正文: 一段时间没写帖子,其实一直在研究策略,只是从不同的角度去思考而已。熟悉我的老板其实清楚,我的炉子水平一般,基本不太依托…...
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:简单网络管理协议 SNMP(Simple Network Management Protocol,简单网络管理协议)是一种用于在计算机网络中管理网络节点(如服务器、工作站、路由器、交换机等)的标准协议。它属于OSI模型的应用层&#…...
ubuntu20.04系统下,c++图形库Matplot++配置
linux下安装c图形库Matplot,使得c可以可视化编程;安装Matplot之前,需要先安装一个gnuplot,因为Matplot是依赖于此库 gnuplot下载链接: http://www.gnuplot.info/ 一、gnuplot下载与安装(可以跳过,下面源码…...
[激光原理与应用-126]:南京科耐激光-激光焊接 - 焊中无损检测技术 - 智能制程监测系统IPM介绍 - 26- 频域分析法
目录 一、什么是频域分析法 1、定义 2、基本原理 3、分析步骤 4、应用领域 5、优缺点 二、频域分析法在激光焊接故障监测中的应用 2.1 概述 1、应用背景 2、频域分析法的应用 3、应用优势 4、应用实例 2.2 激光焊接故障检测中光电信号的频谱特征 1、光电信号分类…...
深入理解 Solidity 修饰符(Modifier):功能、应用与最佳实践
1. 什么是修饰符(Modifier)? 1.1 修饰符的定义 在 Solidity 中,修饰符(Modifier)是一种用于更改函数行为的关键字。它们可以用于控制函数的执行条件、添加前置检查、简化重复逻辑等。修饰符在函数执行之前…...
YOLO11项目实战1:道路缺陷检测系统设计【Python源码+数据集+运行演示】
一、项目背景 随着城市化进程的加速和交通网络的不断扩展,道路维护成为城市管理中的一个重要环节。道路缺陷(如裂缝、坑洞、路面破损等)不仅影响行车安全,还会增加车辆的磨损和维修成本。传统的道路缺陷检测方法主要依赖人工巡检…...
怎么屏蔽统计系统统计到的虚假ip
屏蔽统计系统中的虚假IP是保护网站分析数据准确性的重要措施。以下是一些有效的策略和步骤,可以帮助您过滤掉虚假IP: 1. 识别虚假IP的特征 了解虚假IP的常见特征可以帮助您识别和屏蔽它们: 短时间内高频率访问:虚假IP可能会在短…...
前端开发设计模式——策略模式
目录 一、策略模式的定义和特点 1.定义: 2.特点: 二、策略模式的实现方式 1.定义策略接口: 2.创建具体策略类: 3.定义上下文类: 三、策略模式的应用场景 1.表单验证场景: 2.动画效果切换场景&…...
SysML案例-潜艇
DDD领域驱动设计批评文集>> 《软件方法》强化自测题集>> 《软件方法》各章合集>>...
车辆重识别(2020NIPS去噪扩散概率模型)论文阅读2024/9/27
[2] Denoising Diffusion Probabilistic Models 作者:Jonathan Ho Ajay Jain Pieter Abbeel 单位:加州大学伯克利分校 摘要: 我们提出了高质量的图像合成结果使用扩散概率模型,一类潜变量模型从非平衡热力学的考虑启发。我们的最…...
基于深度学习的任务序列中的快速适应
基于深度学习的任务序列中的快速适应是指模型在接连处理不同任务时,能够迅速调整和优化自身以适应新任务的能力。这种能力在动态环境和多任务学习中尤为重要,旨在减少训练时间和资源需求。以下是这一主题的关键要素: 1. 快速适应的背景 动态…...
虚拟机三种网络模式详解
在电脑里开一台虚拟机,是再常见不过的操作了。无论是用虚拟机玩只有旧版本系统能运行的游戏,还是用来学习Linux、跑跑应用程序都是很好的。而这其中,虚拟机网络是绝对绕不过去的。本篇文章通俗易懂的介绍了常见的虚拟网络提供的三种网络链接模…...
[leetcode]674_最长连续递增序列
给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l < i < r,都有 nums[i] < nums[i 1] &am…...
【无人机设计与技术】四旋翼无人机,UAV仿真,轨迹跟踪PID控制
摘要 本文探讨了四旋翼无人机(UAV)在轨迹跟踪中的PID控制仿真方法。通过设计三轴方向的PID控制器,调节无人机的姿态与位置,使其能够准确跟踪预设轨迹。本文使用MATLAB/Simulink进行了建模与仿真,验证了PID控制算法在无…...
回归预测|基于卷积神经网络-支持向量机的数据回归预测Matlab程序CNN-SVM 卷积提取特征与原始特征进行融合预测
回归预测|基于卷积神经网络-支持向量机的数据回归预测Matlab程序CNN-SVM 卷积提取特征与原始特征进行融合预测 文章目录 一、基本原理原理流程总结 二、实验结果三、核心代码四、代码获取五、总结 回归预测|基于卷积神经网络-支持向量机的数据回归预测Matlab程序CNN-SVM 卷积提…...
javaScript基础知识汇总
一、基础语法 1、区分大小写:无论是变量、函数名还是操作符,都区分大小写。 2、标识符:就是变量、函数、属性或函数参数的名称。标识符可以由一个或多个字符构成,但需要满足以下条件: 第一个字符必须是一个字母、下…...
《动手学深度学习》笔记2.2——神经网络从基础→进阶 (参数管理-每层的权重/偏置)
目录 0. 前言 正文:参数管理 1. 参数访问 1.1 [目标参数] 1.2 [一次性访问所有参数] 1.3 [从嵌套块收集参数] 2. 参数初始化 2.1 [内置初始化] 2.2 [自定义初始化] 2.3 [参数绑定-共享参数] 3. 小结(第2节) 4. 延后初始化 (原书第…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
