LeetCode 169. 多数元素
LeetCode 169. 多数元素
难度:easy\color{Green}{easy}easy
题目描述
给定一个大小为 nnn 的数组 numsnumsnums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊n/2⌋⌊ n/2 ⌋⌊n/2⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:nums = [3,2,3]
输出:3
示例 2:
输入:nums = [2,2,1,1,1,2,2]
输出:2
提示:
- n==nums.lengthn == nums.lengthn==nums.length
- 1<=n<=5∗1041 <= n <= 5 * 10^{4}1<=n<=5∗104
- −109<=nums[i]<=109-10^{9} <= nums[i] <= 10^{9}−109<=nums[i]<=109
进阶: 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
算法1
(哈希)
使用 C++ 提供的 unordered_map 记录每个元素出现的次数。
遍历过程在,如果次数大于 n/2,则返回该数字即可。
复杂度分析
-
时间复杂度:
unordered_map单次插入和查询的时间复杂度为 O(1)O(1)O(1),故总时间复杂度为 O(n)O(n)O(n) -
空间复杂度 : 至少需要额外的 O(n)O(n)O(n) 的空间。
C++ 代码
class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int, int> hash;int n = nums.size();int res = 0;for (int i = 0; i < n; i ++) {hash[nums[i]] ++;if (hash[nums[i]] > n / 2) res = nums[i];}return res;}
};
算法2
(投票算法)
- 定义
cnt计数器,初始为0;candidate记录答案。 - 从头开始遍历数组,若发现
cnt == 0,则candidate := nums[i];然后若candidate == nums[i],cnt++;否则cnt--。 - 遍历结束后,若数组中存在主要元素,则主要元素必定是
candidate。
复杂度分析
-
时间复杂度:仅遍历一次数组,故时间复杂度为 O(n)O(n)O(n)
-
空间复杂度 : 仅使用了两个变量,故需要 O(1)O(1)O(1) 的额外空间。
C++ 代码
class Solution {
public:int majorityElement(vector<int>& nums) {int cnt = 0, candidate;for (int i = 0; i < nums.size(); i ++) {if (cnt == 0) candidate = nums[i];if (nums[i] == candidate) cnt ++;else cnt --;}return candidate;}
};
相关文章:
LeetCode 169. 多数元素
LeetCode 169. 多数元素 难度:easy\color{Green}{easy}easy 题目描述 给定一个大小为 nnn 的数组 numsnumsnums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊n/2⌋⌊ n/2 ⌋⌊n/2⌋ 的元素。 你可以假设数组是非空的,并且给…...
来了,metaIPC1.0
metaRTC推出metaIPC正式版1.0,基于metaRTC6.0最新版二次开发,metaIPC是为嵌入式/摄像头量身打造的webRTC版IPC Camera,可安装在国内大多数Soc芯片上,如在君正/瑞芯微/MSTAR/海思等等已经有多个成熟产品应用。 New Feature 支持M…...
WireShark如何进行USB包协议分析
USB协议学习的步骤之一就是从抓包看协议通信,进而学习usb设备开发是怎么回事。这里发现一个工具就是wireshark。 WireShark如果要抓取usb设备的包,需要在安装的时候,选择usbpcap一并进行安装。...
蒙特卡洛随机模拟
蒙特卡洛随机模拟 简介 蒙特卡洛模拟是在计算机上模拟项目实施了成千上万次,每次输入都随机选择输入值。由于每个输入很多时候本身就是一个估计区间,因此计算机模型会随机选取每个输入的该区间内的任意值,通过大量成千上万甚至百万次的模拟…...
Android从屏幕刷新到View的绘制(三)之Handler异步消息与同步屏障
0. 相关分享 Android从屏幕刷新到View的绘制(一)之 Window、WindowManager和WindowManagerService之间的关系 Android从屏幕刷新到View的绘制(二)之Choreographer、Vsync与屏幕刷新 1. 相关类 Handler Handler中维护着它所在的…...
最新版axios@1.3.x取消请求-AbortController-初体验-番茄出品
最新版axios1.3.x取消请求-AbortController-初体验-番茄出品 start 前文提到,axios 中的取消请求,包含两种方式: AbortController;CancelToken; 上篇文章讲解了 CancelToken,今天这篇文章来了解一下 Abor…...
Git的简述
Git 文章目录GitGit概述版本控制工具集中式管理控制工具分步式管理控制工具控制机制Git和代码托管中心安装Git软件Git常用命令Git概述 Git是一个免费的、开源的分步式版本控制系统,可以快速的处理从小型到大型的各种项目 Git 易于学习,占地面积小&…...
webpack实战,手写loader和plugin
序言 对于 webpack 来说, loader 和 plugin 可以算是需求程度最为广泛的配置项了。但是呢,单单止步于配置可能还不够。如果我们自己有时候想要 diy 一个需求,但是 webpack 又没有相关的 loader 和 plugin 。那这个时候我们可能就得开始造点轮…...
STM32CubeMX按键模块化 点灯
本文代码使用 HAL 库。 文章目录前言一、按键原理图二、CubeMX 创建工程三、代码讲解:1. GPIO的输入HAL库函数:2. 消抖:3. 详细代码四,实验现象:总结前言 我们继续讲解 stm32 f103,这篇文章将详细 为大家讲…...
C#专栏目录(长期更新)
文章目录C# 基础C#进阶C#应用WPF基础WPF 3D小游戏C# 基础 1996年,微软用年薪三百万美刀的价格从Borland挖来了大神海尔斯伯格,开始了J开发,用以对抗Java。但SUN公司认为此举违反了Java开发平台的中立性,对微软提出诉讼。C#正是在…...
BurpSuite配置抓取HTTPS数据包
简介 我们在渗透测试的过程中,经常会遇到HTTPS的网站,Burp默认是没有办法抓取HTTPS的包的,想要让Burp抓取Https的包也很好办,只需要浏览器安装相关的证书即可,接下来将配置过程做一个记录。 前置条件: 1.J…...
图片转base64格式返回给前端,前端如何展示?
图片以base64形式在页面上展示出来在这里要说到Data URI scheme,它可以直接将一些小的数据直接嵌入到网页中,不需要再引入。支持格式如下data:, 文本数据data:text/plain, 文本数据data:text/html, HTML代码data:text/html;base64, base64编码的HTML代码…...
C++入门知识【超详解】
目录1.认识Chello worldC关键字2.命名空间3.std标准库4.输入输出5.缺省参数6.函数重载7.引用7.1引用的概念7.2引用的场景1.作参数2.作返回值7.3引用的注意点7.4指针和引用的区别8.auto关键字9.基于范围的for循环10.内联函数10.1概念10.2特征11. C98中的指针空值1.认识C hello …...
零基础、非计算机系学Python该如何上手?
首先我觉得要放平心态,不用过多去纠结是不是专业出身这回事。 想学那就认真去学,我们最终目标是掌握Python这门技能。 非计算机专业同时零基础,想自学Python该如何上手?分享我自学Python的几点建议吧。 1、重视基础 Python是一…...
关于 vue3 模板引用
文章目录前言1.访问模板引用2.v-for中的模板引用3.组件上的ref前言 如果我们需要直接访问组件中的底层DOM元素,可使用vue提供特殊的ref属性来访问 1.访问模板引用 在视图元素中采用ref属性来设置需要访问的DOM元素 a. 该ref属性可采用字符值的执行设置 b. 该ref属…...
Redis | 安装Redis和启动Redis服务
目录 一、Redis简介 1.1 简介 二、Redis安装 2.1 Windows安装Redis 2.2 Linux安装Redis 三、Redis服务启动和停止 3.1 Windows启动Redis服务 3.2 Linux启动Redis服务 四、Redis设置密码远程连接 4.1 为Redis登陆设置密码 4.2 设置Redis允许远程连接 五、Redis常…...
博客要考虑的最佳WordPress主题
有太多的选择会瘫痪你做决定的能力。有太多的WordPress主题,但仅仅只需要一个并且它是要合适的。我们建立了数十个 WordPress 博客并安装了数百个主题。根据我们所有的经验,我们发现Newspaper是大多数用户的最佳WordPress博客主题。这个自适应、强大的主…...
C 学习笔记 —— 函数指针
函数指针 上面的第二个char (* f) (int);写法就是函数指针的声明; 首先,什么是函数指针?假设有一个指向 int类型变量的指针,该指针储存着这个int类型变量储存在内存位置的地址。 同样,函数也有地址,因为函…...
FastDDS-3. DDS层
3. DDS层 eProsima Fast DDS公开了两个不同的API,以在不同级别与通信服务交互。主要API是数据分发服务(DDS)数据中心发布订阅(DCPS)平台独立模型(PIM)API,简称DDS DCPS PIM…...
9.2 IGMPv2
实验目的 (1) 熟悉IGMPv2的应用场景 (2) 掌握IGMPv2的配置方法 实验拓扑 实验拓扑如图9-17所示: 图9-17:IGMPv2 实验步骤 配置IP地址(请参考上一个实验)运行IGPÿ…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
