【面试经典150题】多数元素
🔗题目链接
✈题目描述:
给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
⌊ n/2 ⌋表示n/2结果向下取整。
🚆数据范围:
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109
🍁思路分析:
因为 ⌊ n 2 ⌋ ≤ n 2 < ⌊ n 2 ⌋ + 1 \lfloor \frac{n}{2} \rfloor \le \frac{n}{2} < \lfloor \frac{n}{2} \rfloor + 1 ⌊2n⌋≤2n<⌊2n⌋+1,所以这个 多数元素 至多只有1个。
🖊解法1:
使用一个辅助对象计数,遍历数组,如果有一个元素的次数超过了 ⌊ n/2 ⌋,即为结果。
/*** @param {number[]} nums* @return {number}*/
var majorityElement = function(nums) {let count={};let flag=Math.floor(nums.length/2);for(let i=0;i<nums.length;i++){if(count[nums[i]]===undefined){count[nums[i]]=0;}count[nums[i]]++;if(count[nums[i]]>flag){return nums[i];}}
};
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)
🖊解法2:
由于多数元素的个数大于其他所有元素总和,所以我们可以从头维护一个候选元素,同时给其计数,遇到同类元素+1,遇到异类元素-1,减为0时,再维护当前元素,再重复之前步骤。
/*** @param {number[]} nums* @return {number}*/
var majorityElement = function(nums) {let candidate=nums[0];let count=1;for(let i=1;i<nums.length;i++){if(count===0){candidate=nums[i];count=1;}else if(candidate===nums[i]){count++;}else{count--;}}return candidate;
};
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
相关文章:
【面试经典150题】多数元素
🔗题目链接 ✈题目描述: 给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 ⌊ n/2 ⌋表示n/2结果向下取…...
c#垃圾回收(Garbage Collection)
在C#中,垃圾回收(Garbage Collection)是一种自动管理内存的机制。它负责跟踪和释放不再使用的内存,以便程序可以有效地使用内存资源。 C#中的垃圾回收器是由.NET运行时(CLR)提供和管理的。它使用了一种叫做…...
vue 基于element-plus el-button封装按钮组件
封装组件的原则是:组件只是数据流通的一个管道,不要糅合太多的逻辑在里面,是一个纯组件,还要根据自己项目的业务场景做具体的处理。 // MyButton.vue // 基于element-plus中el-button来封装按钮 <template><el-button c…...
smbus只能再python2.7下运行?不能再python3.8下运行吗?
不是的,SMBus并不只能在Python 2.7下运行,它也可以在Python 3.8及更高版本下运行。SMBus是用于访问系统上的I2C设备(Inter-Integrated Circuit,一种串行通信协议)的Python库,它应该与Python 3.8兼容。 要在…...
python中is和==的区别
is 和 的区别 在Python中,is和是两个用于比较对象的操作符,它们有不同的作用和用法。 is操作符: is用于比较两个对象的身份标识,即判断两个对象是否引用同一个内存地址的对象。当is操作符用于比较两个对象时,它会判断…...
Viobot回环使用
Viobot回环是使用词袋匹配的方式,,当新的关键帧能够匹配词袋里面记录过的关键帧时,触发回环,将设备的当前位姿拉到历史位姿。 一.上位机操作 词袋使用方法 连接上设备,先停止算法。UI上点 设置 选到 loop 选项卡&…...
React钩子函数之forward结合useImperativeHandle钩子的基本使用
React钩子函数是React框架中非常重要的一部分,其中forward和useImperativeHandle是两个常用的钩子函数。这两个钩子函数可以结合使用,用来实现一些高级的功能。 首先,让我们来了解一下forward钩子函数。它的作用是将父组件中的props传递给子…...
c++中移动语义和完美转发
C 中的移动语义和完美转发是 C11 引入的两个重要特性,它们分别用于提高性能和灵活性。 移动语义(Move Semantics): 移动语义允许有效地将资源(如堆上分配的内存或其他资源)从一个对象转移到另一个对象,而…...
【linux命令讲解大全】040. 文件操作:使用touch命令创建和更新文件
文章目录 touch补充说明语法选项参数示例 从零学 python touch 创建新的空文件或更新已存在文件的时间标签。 补充说明 touch命令具有两个功能: 更新已存在文件的时间标签为当前系统时间(默认方式),文件的数据保持不变。创建新…...
Redis之MoreKey问题及Scan命令解读
目录 MoreKey问题讨论 Scan命令 Sscan命令 Hscan命令 Zscan命令 MoreKey问题讨论 keys * 查看当前库所有key 对于海量数据执行key *会造成严重服务卡顿、影响业务。在实际环境中最好不要使用。生产制造过程中keys * / flushdb/flushall等危险命令以防止误删误用。 大量的…...
QA工具开发流程
前言 在项目上线前期,这边根据需求制作了一套QA测试工具。主要分为以下四个模块的测试**图1** **数值测试:**主要包括了角色的等级变更、游戏里货币的变更、(目前已制作的)游戏道具的数量变更。这些可能归一为一类测试模型**动画…...
JSON.toJSONString首字母大小写问题
前言 开发过程中遇到的,对象转字符串时,有个字段首字母是大写的,转换之后就变成了小写,在这里记录下 代码示例 String jsonString JSON.toJSONString(obj,SerializerFeature.PrettyFormat,SerializerFeature.WriteMapNullValue,…...
ant-vue1.78版a-auto-complete表单自动搜索返回列表中的关键字标红
a-auto-complete表单自动搜索返回列表中的关键字标红 通常在做关键字标红的场景,都是后端返回html结构,前端直接渲染实现,但是如果需要前端处理的话,实现也是很简单的,接下来我直接上应用场景吧 应用场景就是通过关键…...
Elasticsearch 优化
Elasticsearch 优化 2.1硬件选择 Elasticsearch 的基础是 Lucene ,所有的索引和文档数据是存储在本地的磁盘中,具体的 路径可在 ES 的配置文件 ../config/elasticsearch.yml 中配置,如下: #----------------------------…...
spring boot的自动装配原理
spring boot的自动装配原理 解释和使用关键技术思想总结 解释和使用 自动装配是什么:自动将第三方组件的bean装载到ioc容器里,不需要开发人员再去写bean相关的一些配置 spring boot怎么做:在启动类上加SpringBootApplication注解就可以实现自…...
走进低代码平台| iVX-困境之中如何突破传统
前言: “工欲善其事,必先利其器”,找到和使用一个优质的工具平台,往往会事半功倍。 文章目录 1️⃣认识走近低代码2️⃣传统的低代码开发3️⃣无代码编辑平台一个代码生成式低代码产品iVX受面性广支持代码复用如何使用? 4️⃣总结…...
【UIPickerView案例03-点餐系统之随机点餐 Objective-C语言】
一、先来看看我们这个示例程序里面,随机点餐是怎么做的 1.点击:“随机点餐”按钮 大家能想到,它是怎么实现的吗 1)首先,点击”随机点餐“按钮,的时候,你要让这个pickerView,进行随机选中,那么,得监听它的点击 2)然后呢,让pickeView选中数据, 3)然后呢,把那个…...
论文阅读_扩散模型_SDXL
英文名称: SDXL: Improving Latent Diffusion Models for High-Resolution Image Synthesis 中文名称: SDXL:改进潜在扩散模型的高分辨率图像合成 论文地址: http://arxiv.org/abs/2307.01952 代码: https://github.com/Stability-AI/generative-models 时间: 2023-…...
云原生Kubernetes:二进制部署K8S多Master架构(三)
目录 一、理论 1.K8S多Master架构 2.配置master02 3.master02 节点部署 4.负载均衡部署 二、实验 1.环境 2.配置master02 3.master02 节点部署 4.负载均衡部署 三、总结 一、理论 1.K8S多Master架构 (1) 架构 2.配置master02 (1)环境 关闭防…...
任意文件读取和下载
任意文件读取是什么? 一些网站的需求,可能会提供文件查看与下载的功能。如果对用户查看或下载的文件没有限制或者限制绕就可以查看或下载任意文件。这些文件可以是源代码文件配置文件敏感文件等等。过, 任意文件读取会造成(敏感)信息泄露;任意…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
