【12_多数元素】
问题
给定一个大小为 n 的数组 nums ,返回其中的多数元素。
多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。
思路
使用摩尔投票算法来解决。该算法的基本思想是维护一个候选人和一个计数器。遍历数组,如果当前元素与候选人相同,则计数器加1;否则,计数器减1。如果计数器变为0,则更新候选人并将计数器重置为1。最终,候选人就是多数元素。
算法
class Solution:def majorityElement(self, nums: list[int]) -> int:n = 0m = Nonefor num in nums:if n == 0:m = numn += (m == num)- (m != num)return m
时间复杂度和空间复杂度
时间复杂度:时间复杂度是用来描述算法执行时间随着输入规模增长的变化趋势的。它主要关注算法中基本操作的执行次数。为了计算时间复杂度,我们可以按照以下步骤进行:确定算法中的基本操作:
1、首先要确定算法中最基本的操作,例如加法、减法、赋值、比较等。
2、写出算法的伪代码或真实代码:将算法用伪代码或真实代码表示出来,以便更好地理解算法的执行过程。
3、标记循环和递归结构:找出算法中的循环和递归结构,这些结构通常会对算法的时间复杂度产生较大影响。
4、计算每个基本操作的执行次数:对于每个基本操作,计算它在最坏情况下被执行的次数。最坏情况是指输入数据使得算法的执行时间最长的情况。
5、使用大 O 符号表示时间复杂度:将算法的时间复杂度表示为大 O 符号的形式,例如 O(n)、O(nlogn)、O(n^2) 等。常用:
1、O(n)
这些算法的执行时间与输入规模 n 成正比。线性搜索:在一个未排序的数组中查找特定元素。
计算数组和:计算一个数组中所有元素的总和。
计数排序:对一组整数进行排序,假设整数的范围有限。
遍历链表:遍历一个链表中的所有节点。2、O(nlogn)
这些算法的执行时间随着输入规模 n 的增长而以对数级别增加。快速排序:对一组数据进行排序。
合并排序:对一组数据进行排序。
堆排序:对一组数据进行排序。
二分查找:在一个已排序的数组中查找特定元素。3、O(n^2)
这些算法的执行时间随着输入规模 n 的增长而以平方级别增加。冒泡排序:对一组数据进行排序。
选择排序:对一组数据进行排序。
插入排序:对一组数据进行排序。
简单的矩阵乘法:计算两个矩阵的乘积。
空间复杂度空间复杂度是用来描述算法在执行过程中所需的额外空间随着输入规模增长的变化趋势的。它主要关注算法中使用的额外空间的大小。为了计算空间复杂度,我们可以按照以下步骤进行:1、确定算法中使用的额外空间:
首先要确定算法在执行过程中使用的额外空间,例如数组、链表、栈、队列等数据结构。
2、计算每种数据结构的空间需求:
对于每种数据结构,计算它在最坏情况下所需的空间大小。最坏情况是指输入数据使得算法使用的空间最大化的情况。
3、使用大 O 符号表示空间复杂度:
将算法的空间复杂度表示为大 O 符号的形式,例如 O(1)、O(n)、O(n^2) 等。
常数级别的额外空间来存储临时变量,空间复杂度为 O(1)。1、O(1)
这些算法或数据结构的空间需求不随输入规模 n 的增长而增加,总是保持常数级别。交换两个变量的值:使用一个临时变量来交换两个变量的值。
计算数组的最大值或最小值:遍历整个数组,记录最大值或最小值。
检查一个数是否是质数:只需要使用几个变量来存储中间结果。2、O(n)
这些算法或数据结构的空间需求随着输入规模 n 的增长而线性增加。线性搜索:在一个未排序的数组中查找特定元素。
创建一个动态数组:创建一个可以动态增长的数组来存储数据。
链表:每个节点都需要存储指向下一个节点的指针和数据本身。
哈希表:哈希表的大小通常与输入规模成正比。3、O(n^2)
这些算法或数据结构的空间需求随着输入规模 n 的增长而以平方级别增加。简单的矩阵乘法:计算两个矩阵的乘积,结果矩阵的大小是 n^2。
邻接矩阵表示的图:每个节点都需要一个大小为 n 的数组来表示与其他节点的连接关系。4、O(nlogn)
这些算法或数据结构的空间需求随着输入规模 n 的增长而以对数级别增加。平衡二叉搜索树:如 AVL 树、红黑树等,虽然在最坏情况下可能退化为链表,但平均情况下空间复杂度仍然是 O(nlogn)。
堆排序:在堆排序过程中,需要使用一个大小为 n 的数组来存储堆。
学习
一、摩尔投票算法(Moore Voting Algorithm)是一种用于在一个未排序的数组中找到出现次数超过一半的元素的高效算法。这个算法的核心思想是利用计数器来跟踪当前候选人的票数。二、算法描述:
1)初始化计数器和候选人:将计数器 count 初始化为 0,并将候选人 candidate 设置为数组的第一个元素。
2)遍历数组:从数组的第二个元素开始,遍历整个数组。
3)更新计数器和候选人:
如果当前元素与候选人相同,则将计数器加 1。
如果当前元素与候选人不同,则将计数器减 1。
如果计数器变为 0,说明之前的候选人已经被淘汰,需要选择一个新的候选人。将候选人更新为当前元素,并将计数器重置为 1。
4)返回候选人:遍历完整个数组后,返回最终的候选人 candidate,即出现次数超过一半的元素。三、算法分析
摩尔投票算法的时间复杂度是 O(n),其中 n 是数组的长度。空间复杂度是 O(1),因为只使用了常数级别的额外空间来存储候选人和计数器。四、这个算法的正确性可以通过以下两点来解释:1、**如果存在一个出现次数超过一半的元素,那么它一定会被选为候选人。**这是因为在遍历过程中,如果当前元素与候选人不同,它的票数会减少;但如果存在一个元素出现次数超过一半,那么在遍历的过程中,它的票数总是会大于或等于其他元素的票数,直到最后。2、**如果不存在一个出现次数超过一半的元素,那么算法返回的候选人可能不是正确答案。**在这种情况下,需要再次遍历数组来验证候选人的出现次数是否真的超过一半。
相关文章:
【12_多数元素】
问题 给定一个大小为 n 的数组 nums ,返回其中的多数元素。 多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。 思路 使用摩尔投票算法来解决。该算法的基本思想是维护一个候选人和一个…...
深入理解 Android 中的 ActivityInfo
深入理解 Android 中的 ActivityInfo 在 Android 开发中,ActivityInfo 是一个非常重要的类,它包含了关于 Activity 的元信息。这些信息通常是从 AndroidManifest.xml 文件中提取的,开发者可以通过 ActivityInfo 类来获取和操作这些信息。本文…...
【通识安全】煤气中毒急救的处置
1.煤气中毒的主要症状与体征一氧化碳中毒,其中毒症状一般分为轻、中、重三种。 (1)轻度:仅有头晕、头痛、眼花、心慌、胸闷、恶心等症状。如迅速打开门窗,或将病人移出中毒环境,使之吸入新鲜空气和休息,给些热饮料&am…...
windows从0开始配置llamafactory微调chatglm3-6b
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 一、准备工作1、创建python虚拟环境(annoconda)2、配置pytorch傻瓜版3、llamafactory配置4、微调数据准备 一、准备工作 1、创建python虚拟环境(annoconda) 本篇文…...
IM-Magic Partition Resizer(分区调整软件) v7.5.0 多语便携版
IM-Magic Partition Resizer是一款功能强大的分区调整软件,允许用户调整并重新分配硬盘分区空间,从而在不丢失数据的情况下改变分区的大小和位置。 软件功能 支持调整和重新分配硬盘分区的空间大小。能够将分区扩大或缩小而不会导致数据丢失。可以改变分…...
matlab中高精度计算函数vpa与非厄米矩阵本征值的求解
clear;clc;close all tic %并行设置% delete(gcp(nocreate));%关闭之前的并行 cparcluster(local); c.NumWorkers50;%手动设置线程数(否则默认最大线程为12) parpool(c, c.NumWorkers); %并行设置%w1; u2.5;N30;valstozeros(2*N2,100); v10linspace(-3,3,100).;parfor jj1:leng…...
流程图(四)利用python绘制漏斗图
流程图(四)利用python绘制漏斗图 漏斗图(Funnel Chart)简介 漏斗图经常用于展示生产经营各环节的关键数值变化,以较高的头部开始,较低的底部结束,可视化呈现各环节的转化效率与变动大小。一般重…...
Elasticsearch:索引mapping
这里写目录标题 一、介绍二、动态mapping三、mapping属性(1)analyzer(分析器)(2) coerce(强制类型转换)(3)copy_to(合并参数) 一、介绍 二、动态mapping 三…...
AI赋能跨境电商:魔珐科技3D数字人破解出海痛点
跨境出海进入狂飙时代,AI应用正在深度渗透并重塑着跨境电商产业链的每一个环节,迎来了发展的高光时刻。生成式AI时代的大幕拉开,AI工具快速迭代,为跨境电商行业的突破与飞跃带来了无限可能性。 由于跨境电商业务自身特性鲜明&…...
计算机网络之---信号与编码
信号 在物理层,信号是用来传输比特流的物理量,它可以是电压、电流、光强度等形式,通常通过电缆、光纤或者无线信道等媒介传播。 信号主要分为以下两种类型: 模拟信号(Analog Signal):信号在时间…...
腾讯云AI代码助手编程挑战赛-FinChat
作品简介 FinChat 是一款极具创新性的智能股票分析工具,依托国内顶尖大语言模型打造而成。它专为日常忙碌、无暇顾及金融市场,却又手握闲钱渴望投资的人群量身定制。核心功能包括: 自动剖析股票数据:迅速生成深度专业研报。实时…...
2025年PMP考试最新报名通知
经PMI和中国国际人才交流基金会研究决定,中国大陆地区2025年第一期PMI认证考试定于3月15日举办。在基金会网站报名参加本次PMI认证考试的考生须认真阅读下文,知悉考试安排及注意事项,并遵守考试有关规定。 一、时间安排 (一&#…...
蓝凌EIS智慧协同平台 fi_message_receiver.aspx SQL注入漏洞复现(CVE-2025-22214)
0x01 产品简介 蓝凌EIS智慧协同平台是一款专为成长型企业打造的沟通、协同、社交的移动办公平台,旨在提升企业内部沟通、协作和信息共享的效率。该平台集成了各种协同工具和功能,全面满足企业的办公需求。具体来说,它覆盖了审批、流程、财务、行政、人事、客户等全在线业务…...
我用AI学Android Jetpack Compose之入门篇(2)
我跑成功了第一个Compose应用,但我还是有很多疑问,请人工智能来解释一下吧。答案来自 通义千问 文章目录 1.请解释一下Compose项目的目录结构。根目录模块目录(通常是app)app/build.gradleapp/src/mainapp/src/main/uiapp/src/ma…...
确认2D Tilemap Editor安装后仍然没有基础的Tile
Create > 2D 新建里面什么Tile类型都有,就是没有最基础的Tile。 在Assets文件夹中,点击右键 > Create > C# Script,新建一个脚本,代码内容复制粘贴进去 using UnityEngine; using UnityEngine.Tilemaps;[CreateAssetMe…...
flutter 独立开发之笔记
1、# use: - [flutter_launcher_icons:] 每次修改完icon后,都需要执行一遍 dart run flutter_launcher_icons 2、开启混淆并打包apk flutter build apk --obfuscate --split-debug-info./out/android/app.android-arm64.symbols 3、开启windows支持 flutter con…...
234.回文链表
234.回文链表 思路1:双指针 1.一次遍历记录链表的值到数组中 2.数组头尾双指针开始判断 复杂度: 时间O(n),空间O(n) 代码: class Solution { public:bool isPalindrome(ListNode* head) {vector<int>nums;while(head){nums.push…...
02、Redis的安装与配置
一、安装配置CentOS7 第一步:安装虚拟机 这个步比较简单,直接安装好VMware和使用CentOS7的镜像安装操作系统 相关资源如果有需要可以在如下位置下载: VMare虚拟机:VMare工具 CentOS7镜像:CentOS7镜像 JDK17_linux-x64:JDK17_linux-x64 linux服务器连接工具:MobaX…...
自动驾驶相关知识学习笔记
一、概要 因为想知道SIL、HIL是什么仿真工具,故而浏览了自动驾驶相关的知识。 资料来源《自动驾驶——人工智能理论与实践》胡波 林青 陈强 著;出版时间:2023年3月 二、图像的分类、分割与检测任务区别 如图所示,这些更高阶的…...
虹软人脸识别
虹软人脸识别 一.虹软人脸识别1. 获取APP_ID与SDK_KEY2. 获取SDK二.Spring整合1. jar包引入2. yaml配置3. 配置类4. 工具类5. api接口6. 启动加载三.前端四.相关文献一.虹软人脸识别 开发者平台 1. 获取APP_ID与SDK_KEY 2. 获取SDK 开发文档 jar包与dll文件...
【Unity笔记】如何把语言修改为简体中文?
方法1: 打开unity hub--------->点击安装--------------->点击你正在使用引擎的设置按钮(右面)------------>点击添加模块------------>最下面语言包,下载简体中文。 方法2: https://new-translate.unit…...
在Nvidia Jetson ADX Orin中使用TensorRT-LLM运行llama3-8b
目录 背景:步骤 1.获取模型权重第 2 步:准备第 3 步:构建 TensorRT-LLM 引擎 背景: 大型语言模型 (LLM) 推理的关键瓶颈在于 GPU 内存资源短缺。因此,各种加速框架主要强调减少峰值 GPU 内存使…...
图数据库管理系统(Graph DBMS)全面解析
目录 前言1. 图数据库管理系统概述1.1 图数据库的基本组成1.2 图数据库的工作原理 2. 图数据库的特点与优势2.1 高效处理复杂关系数据2.2 灵活的数据建模2.3 优越的查询性能2.4 支持大规模分布式存储 3. 图数据库的应用场景3.1 社交网络3.2 推荐系统3.3 金融风控3.4 网络与IT运…...
中华人民共和国预算法实施条例
(1995年11月2日国务院第37次常务会议通过 1995年11月22日中华人民共和国国务院令第186号发布 自发布之日起施行) 第一章 总则 第一条 根据《中华人民共和国预算法》(以下简称预算法),制定本条例。 第二条 县级以上地方政府的派出机关,根据本级政…...
LabVIEW专栏十、工厂模式
目录 一、工厂模式1.1、创建仪器管理类1.2、初始化1.3、方法1.3.1、set devices1.3.2、index to device 1.4、释放资源 二、测试管理类2.1、界面2.2、程序框图2.2.1、初始化2.2.2、索引仪器 该章介绍一种设计模式"工厂模式",新建一个仪器管理类࿰…...
基于SpringBoot的斯诺克球馆预约购票管理系统
作者:计算机学姐 开发技术:SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等,“文末源码”。 专栏推荐:前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏:…...
C# 设计模式(行为型模式):命令模式(专注于撤销重做)
C# 设计模式(行为型模式):命令模式 (Command Pattern) 一、什么是命令模式? 命令模式(Command Pattern)是一种行为型设计模式,它将请求封装成一个对象,从而使你可以用不同的请求、队…...
牛客网刷题 ——C语言初阶(2分支和循环-for)——打印菱形
1. 题目描述 用C语言在屏幕上输出以下图案: 2. 思路 我是先上手,先把上半部分打印出来,然后慢慢再来分析,下面这是我先把整个上半部分打印出来,因为空格不方便看是几个,这里先用&代替空格了 然后这里…...
[ LeetCode 75 ] 1768. 交替合并字符串
题目描述:(相关标签:双指针、字符串) 给你两个字符串 word1 和 word2 。请你从 word1 开始,通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长,就将多出来的字母追加到合并后字符串的末尾。 返…...
【Java】——方法
方法(method)是程序中最小的执行单元 eg:main方法 作用: 提高代码的复用性、提高代码的可维护性 方法的格式: 将代码打包在一起,该过程称为方法定义 方法调用: 方法定义后并不是直接运行&am…...
Koi技术教程-Tauri基础教程-第一节 Tauri项目创建及结构说明
1 “你日渐平庸,甘于平庸,将继续平庸。”——《以自己喜欢的方式过一生》 2. “总是有人要赢的,那为什么不能是我呢?”——科比布莱恩特 3. “你那么憎恨那些人,和他们斗了那么久,最终却要变得和他们一样,…...
《Mcal》--MCU模块
一、MCU模块的主要功能 控制系统时钟的产生。控制系统通用模块,该模块会涉及到Adc、Ftm等外设的配置。控制外设时钟。控制MCU运行的模式。初始化定义RAM Section。 比较重要的是时钟的配置。 二、系统时钟的配置 1、芯片时钟树 要想弄明白时钟配置,需…...
大模型思维链推理的进展、前沿和未来分析
大模型思维链推理的综述:进展、前沿和未来 "Chain of Thought Reasoning: A State-of-the-Art Analysis, Exploring New Horizons and Predicting Future Directions." 思维链推理的综述:进展、前沿和未来 摘要:思维链推理&#…...
windows上利用MinGW编译hiredis
1、下载 hiredis https://github.com/redis/hiredis 2、利用CMake生成Makefile文件 CMAKE_BUILD_TYPE: 默认空的时候是Release的。如果需要Debug则自行修改。 执行Configure的时候选择MinGW(确保MinGW已经安装,并且已加入到环境变量) 3、执行…...
06-RabbitMQ基础
目录 1.初识MQ 1.1.同步调用 1.2.异步调用 1.3.技术选型 2.RabbitMQ 2.1.安装 2.2.收发消息 2.2.1.交换机 2.2.2.队列 2.2.3.绑定关系 2.2.4.发送消息 2.3.数据隔离 2.3.1.用户管理 2.3.2.virtual host 3.SpringAMQP 3.1.导入Demo工程 3.2.快速入门 3.2.1.消…...
Spring Boot 的自动配置,以rabbitmq为例,请详细说明
Spring Boot 的自动配置特性能够大大简化集成外部服务和组件的配置过程。以 RabbitMQ 为例,Spring Boot 通过 spring-boot-starter-amqp 提供了自动配置支持,开发者只需在应用中添加相关依赖并配置必要的属性,Spring Boot 会自动配置所需的连…...
ros2-4.1 服务通信介绍
服务是ROS图中节点之间的另一种通信方法。服务分为客户端和服务端,客户端发送请求给服务端,服务端可以根据客户端的请求做一些处理,然后返回结果给客户端。也称为为请求-响应模型。 服务和话题的不同之处,话题是没有返回的&#…...
如何 cURL Elasticsearch:进入 Shell
作者:来自 Elastic Philipp Krenn Kibana 的控制台是开始使用 Elasticsearch 的 REST API 的最简单方法 - 语法突出显示、自动完成、格式化、导出 cURL、JavaScript 或 Python。而且你不必担心正确的端点、身份验证等。但是有时,如果 Kibana 不可用、你…...
【信息系统项目管理师】高分论文:论信息系统项目的风险管理(人民医院的信息系统)
更多内容请见: 备考信息系统项目管理师-专栏介绍和目录 文章目录 论文1、规划风险管理2、项目风险识别3、风险定性分析4、风险定量分析5、制定风险应对6、实施风险应对计划7、监督风险论文 2022年6月,我作为项目经理承担了XX县人民医院的信息系统建设,该项目总投资300万,其…...
安装和配置 Apache 及 PHP
安装和配置 Apache 及 PHP # 1. 停止当前 Apache 服务 sudo apachectl stop# 2. 清除现有的 Apache 配置和文件 sudo rm -rf /etc/apache2 sudo rm -rf /usr/sbin/httpd sudo rm -rf /Library/WebServer# 3. 使用 Homebrew 安装 Apache brew install httpd# 4. 启动 Apache su…...
jenkins入门12-- 权限管理
Jenkins的权限管理 由于jenkins默认的权限管理体系不支持用户组或角色的配置,因此需要安装第三发插件来支持角色的配置,我们使用Role-based Authorization Strategy 插件 只有项目读权限 只有某个项目执行权限...
虚功、达朗贝尔原理和拉格朗日方程
本文先引入虚位移,从虚功和虚功原理出发,介绍达朗贝尔原理(d’Alembert’s principle) 和 拉格朗日方程(Lagrange’s equations)。 1. 虚功 力学系统的虚位移(virtual displacement)或称无限小位移(infinitesimal displacement)是指力学系统的位形(configuration …...
面向对象分析和设计OOA/D,UML,GRASP
目录 什么是分析和设计? 什么是面向对象的分析和设计? 迭代开发 UML 用例图 交互图 基于职责驱动设计 GRASP 常见设计原则 什么是分析和设计? 分析,强调是对问题和需求的调查研究,不是解决方案。例如&#x…...
【Linux】记录一下考RHCE的学习过程(七)
年底了,公司接的北京地铁轨道交通的项目做不完了,一百多列地铁的设备都得调,派我出差了几周,这几天才回来,出差累死了实在是没办法更新。(YOASOBI的二开票还没抢到ToT,哭死,看看回滚…...
【深度学习】深度(Deep Learning)学习基础
深度学习(Deep Learning) 深度学习是一种基于人工神经网络的机器学习方法,通过多个层次(深度)的神经网络从数据中自动学习特征和模式。它是人工智能的一个核心领域,尤其在处理复杂数据(如图像、…...
121 买入股票的最佳时机
思路1: 买的那天一定是卖的那天之前的最小值。 每到一天,维护那天之前的最小值即可。 假设第一天是最小值,最大值初始化为0,当以后某天的价格小于最小值时,将最小值更新 当天价格大于最小值,说明有利可图…...
JVM之Java内存模型
Java内存模型(Java Memory Model,简称JMM)是Java虚拟机(JVM)规范中定义的一套规则,用于描述多线程环境下变量如何被访问和同步。在多线程编程中,内存模型的重要性不言而喻,它直接关系…...
matlab系列专栏-快捷键速查手册
目录 1在命令窗口(Command Window)中 2. 在编辑器(Editor)(m文件)中 1在命令窗口(Command Window)中 1)【↑、↓】——切换到之前、之后运行过的命令,可以重复按多次来达到想要的命令。 2)【Tab】——自动补全。在Command窗口,…...
快手一面-面经
1. RPC和Http的区别? RPC(Remote Procedure Call,远程过程调用)和 HTTP(HyperText Transfer Protocol,超文本传输协议)是两种不同的通信机制,它们有不同的用途、工作原理和应用场景…...
<style lang=“scss“ scoped>: 这是更常见的写法,也是官方文档中推荐的写法
这两种写法在大多数情况下是没有区别的,它们都是 Vue.js 单文件组件 (.vue 文件) 中用来定义组件私有样式的方式。 两种写法: <style lang"scss" scoped>: 这是更常见的写法,也是官方文档中推荐的写法。<style scoped l…...