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

【面试经典150题】多数元素

🔗题目链接

题目描述

给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

⌊ n/2 ⌋表示n/2结果向下取整。

🚆数据范围

  • n == nums.length
  • 1 <= 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 2n2n<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题】多数元素

&#x1f517;题目链接 ✈题目描述&#xff1a; 给定一个大小为 n 的数组 nums &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。 ⌊ n/2 ⌋表示n/2结果向下取…...

c#垃圾回收(Garbage Collection)

在C#中&#xff0c;垃圾回收&#xff08;Garbage Collection&#xff09;是一种自动管理内存的机制。它负责跟踪和释放不再使用的内存&#xff0c;以便程序可以有效地使用内存资源。 C#中的垃圾回收器是由.NET运行时&#xff08;CLR&#xff09;提供和管理的。它使用了一种叫做…...

vue 基于element-plus el-button封装按钮组件

封装组件的原则是&#xff1a;组件只是数据流通的一个管道&#xff0c;不要糅合太多的逻辑在里面&#xff0c;是一个纯组件&#xff0c;还要根据自己项目的业务场景做具体的处理。 // MyButton.vue // 基于element-plus中el-button来封装按钮 <template><el-button c…...

smbus只能再python2.7下运行?不能再python3.8下运行吗?

不是的&#xff0c;SMBus并不只能在Python 2.7下运行&#xff0c;它也可以在Python 3.8及更高版本下运行。SMBus是用于访问系统上的I2C设备&#xff08;Inter-Integrated Circuit&#xff0c;一种串行通信协议&#xff09;的Python库&#xff0c;它应该与Python 3.8兼容。 要在…...

python中is和==的区别

is 和 的区别 在Python中&#xff0c;is和是两个用于比较对象的操作符&#xff0c;它们有不同的作用和用法。 is操作符&#xff1a; is用于比较两个对象的身份标识&#xff0c;即判断两个对象是否引用同一个内存地址的对象。当is操作符用于比较两个对象时&#xff0c;它会判断…...

Viobot回环使用

Viobot回环是使用词袋匹配的方式&#xff0c;&#xff0c;当新的关键帧能够匹配词袋里面记录过的关键帧时&#xff0c;触发回环&#xff0c;将设备的当前位姿拉到历史位姿。 一.上位机操作 词袋使用方法 连接上设备&#xff0c;先停止算法。UI上点 设置 选到 loop 选项卡&…...

React钩子函数之forward结合useImperativeHandle钩子的基本使用

React钩子函数是React框架中非常重要的一部分&#xff0c;其中forward和useImperativeHandle是两个常用的钩子函数。这两个钩子函数可以结合使用&#xff0c;用来实现一些高级的功能。 首先&#xff0c;让我们来了解一下forward钩子函数。它的作用是将父组件中的props传递给子…...

c++中移动语义和完美转发

C 中的移动语义和完美转发是 C11 引入的两个重要特性&#xff0c;它们分别用于提高性能和灵活性。 移动语义&#xff08;Move Semantics&#xff09;: 移动语义允许有效地将资源&#xff08;如堆上分配的内存或其他资源&#xff09;从一个对象转移到另一个对象&#xff0c;而…...

【linux命令讲解大全】040. 文件操作:使用touch命令创建和更新文件

文章目录 touch补充说明语法选项参数示例 从零学 python touch 创建新的空文件或更新已存在文件的时间标签。 补充说明 touch命令具有两个功能&#xff1a; 更新已存在文件的时间标签为当前系统时间&#xff08;默认方式&#xff09;&#xff0c;文件的数据保持不变。创建新…...

Redis之MoreKey问题及Scan命令解读

目录 MoreKey问题讨论 Scan命令 Sscan命令 Hscan命令 Zscan命令 MoreKey问题讨论 keys * 查看当前库所有key 对于海量数据执行key *会造成严重服务卡顿、影响业务。在实际环境中最好不要使用。生产制造过程中keys * / flushdb/flushall等危险命令以防止误删误用。 大量的…...

QA工具开发流程

前言 在项目上线前期&#xff0c;这边根据需求制作了一套QA测试工具。主要分为以下四个模块的测试**图1** **数值测试&#xff1a;**主要包括了角色的等级变更、游戏里货币的变更、&#xff08;目前已制作的&#xff09;游戏道具的数量变更。这些可能归一为一类测试模型**动画…...

JSON.toJSONString首字母大小写问题

前言 开发过程中遇到的&#xff0c;对象转字符串时&#xff0c;有个字段首字母是大写的&#xff0c;转换之后就变成了小写&#xff0c;在这里记录下 代码示例 String jsonString JSON.toJSONString(obj,SerializerFeature.PrettyFormat,SerializerFeature.WriteMapNullValue,…...

ant-vue1.78版a-auto-complete表单自动搜索返回列表中的关键字标红

a-auto-complete表单自动搜索返回列表中的关键字标红 通常在做关键字标红的场景&#xff0c;都是后端返回html结构&#xff0c;前端直接渲染实现&#xff0c;但是如果需要前端处理的话&#xff0c;实现也是很简单的&#xff0c;接下来我直接上应用场景吧 应用场景就是通过关键…...

Elasticsearch 优化

Elasticsearch 优化 2.1硬件选择 Elasticsearch 的基础是 Lucene &#xff0c;所有的索引和文档数据是存储在本地的磁盘中&#xff0c;具体的 路径可在 ES 的配置文件 ../config/elasticsearch.yml 中配置&#xff0c;如下&#xff1a; #----------------------------…...

spring boot的自动装配原理

spring boot的自动装配原理 解释和使用关键技术思想总结 解释和使用 自动装配是什么&#xff1a;自动将第三方组件的bean装载到ioc容器里&#xff0c;不需要开发人员再去写bean相关的一些配置 spring boot怎么做&#xff1a;在启动类上加SpringBootApplication注解就可以实现自…...

走进低代码平台| iVX-困境之中如何突破传统

前言&#xff1a; “工欲善其事,必先利其器”&#xff0c;找到和使用一个优质的工具平台&#xff0c;往往会事半功倍。 文章目录 1️⃣认识走近低代码2️⃣传统的低代码开发3️⃣无代码编辑平台一个代码生成式低代码产品iVX受面性广支持代码复用如何使用&#xff1f; 4️⃣总结…...

【UIPickerView案例03-点餐系统之随机点餐 Objective-C语言】

一、先来看看我们这个示例程序里面,随机点餐是怎么做的 1.点击:“随机点餐”按钮 大家能想到,它是怎么实现的吗 1)首先,点击”随机点餐“按钮,的时候,你要让这个pickerView,进行随机选中,那么,得监听它的点击 2)然后呢,让pickeView选中数据, 3)然后呢,把那个…...

论文阅读_扩散模型_SDXL

英文名称: SDXL: Improving Latent Diffusion Models for High-Resolution Image Synthesis 中文名称: SDXL&#xff1a;改进潜在扩散模型的高分辨率图像合成 论文地址: 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 &#xff08;1&#xff09;环境 关闭防…...

任意文件读取和下载

任意文件读取是什么&#xff1f; 一些网站的需求&#xff0c;可能会提供文件查看与下载的功能。如果对用户查看或下载的文件没有限制或者限制绕就可以查看或下载任意文件。这些文件可以是源代码文件配置文件敏感文件等等。过&#xff0c; 任意文件读取会造成(敏感)信息泄露;任意…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...