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

Leetcode:【169. 多数元素】

题目

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

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

难度:简单

题目链接:169. 多数元素

示例 1:

输入:nums = [3,2,3]
输出:3

示例 2:

输入:nums = [2,2,1,1,1,2,2]
输出:2

提示:

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

进阶:尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

代码展示

int majorityElement(int* nums, int numsSize){int king = nums[0];//假设第一个是多数元素int votes = 1;int i = 0;for( i = 0;i<numsSize;i++){if(nums[i] == king)votes++;else{votes--;if(votes == 0){king = nums[i];//多数元素votes = 1;//票数重置}}}return king;
}

 【解析】

这里采用的 进阶的做法(时间复杂度为 O(n)、空间复杂度为 O(1) )

采用的是 摩尔投票法

简单地介绍一下摩尔投票法

摩尔投票法:

核心就是对拼消耗。

玩一个诸侯争霸的游戏,假设你方人口超过总人口一半以上,并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。

那就大混战呗,最差所有人都联合起来对付你(对应你每次选择作为计数器的数都是众数),或者其他国家也会相互攻击(会选择其他数作为计数器的数),但是只要你们不要内斗,最后肯定你赢。

最后能剩下的必定是自己人

其实可以 在nums数组中 元素可以这样区分 友军(相同元素),敌军(不同元素)。遇到相同元素加1,不用元素减1。

相关文章:

Leetcode:【169. 多数元素】

题目 给定一个大小为 n 的数组 nums &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。 难度&#xff1a;简单 题目链接&#xff1a;169. 多数元素 示例 1&#xff…...

好用免费的Chat GPT

MindLink麦灵 你问我答 灵感 持续更新中。。。。...

MySQL-MHA

目录 1、什么是 MHA 2、MHA 的组成 3、MHA 的特点 3.1 MHA工作原理总结如下 4、搭建 MySQL MHA 4.1 实验环境配置 MHA架构 故障模拟 4.2 安装MHA所有组件 4.3 故障模拟 4.4 总结 1、什么是 MHA MHA&#xff08;MasterHigh Availability&#xff09;是一套优秀的My…...

初识Node.js与内置模块

1. 初识 Node.js 1.1 回顾与思考 1. 已经掌握了哪些技术 2. 浏览器中的 JavaScript 的组成部分 3. 思考&#xff1a;为什么 JavaScript 可以在浏览器中被执行 4. 思考&#xff1a;为什么 JavaScript 可以操作 DOM 和 BOM 5. 浏览器中的 JavaScript 运行环境 6. 思考&#xff…...

NLP(1)--NLP基础与自注意力机制

目录 一、词向量 1、概述 2、向量表示 二、词向量离散表示 1、one-hot 2、Bag of words 3、TF-IDF表示 4、Bi-gram和N-gram 三、词向量分布式表示 1、Skip-Gram表示 2、CBOW表示 四、RNN 五、Seq2Seq 六、自注意力机制 1、注意力机制和自注意力机制 2、单个输出…...

Ubuntu 升级cuda版本与切换

下载cuda版本 进&#xff1a;CUDA Toolkit 12.2 Downloads | NVIDIA Developer wget https://developer.download.nvidia.com/compute/cuda/12.2.0/local_installers/cuda_12.2.0_535.54.03_linux.runsudo sh ./cuda_12.2.0_535.54.03_linux.run --toolkit --silent --overrid…...

精讲算法的时间复杂度

目录 一、算法效率 1.算法效率 1.1如何衡量一个算法的好坏 1.2算法的复杂度 二、时间复杂度 1.时间复杂度的概念 2.大O的渐进表示法 3.常见时间复杂度的计算举例 三、空间复杂度 一、算法效率 1.算法效率 1.1如何衡量一个算法的好坏 long long Fib(int N) {if(N <…...

java八股文面试[多线程]——newWorkStealingPool

newWorkStealingPool是什么&#xff1f; newWorkStealingPool简单翻译是任务窃取线程池。 newWorkStealingPool 是Java8添加的线程池。和别的4种不同&#xff0c;它用的是ForkJoinPool。 使用ForkJoinPool的好处是&#xff0c;把1个任务拆分成多个“小任务”&#xff0c;把这…...

STM32--RTC实时时钟

文章目录 Unix时间戳时间戳转换BKPRTC简介RTC框图硬件电路RTC的注意事项RTC时钟实验工程 Unix时间戳 Unix 时间戳是从1970年1月1日&#xff08;UTC/GMT的午夜&#xff09;开始所经过的秒数&#xff0c;不考虑闰秒。 时间戳存储在一个秒计数器中&#xff0c;秒计数器为32位/64…...

【N2】例题学习笔记

N2例题 《新"日本语能力测试"例题集》 听力原稿(PDF) 【10】 【問い】この筆者から見た「仕事ができる人」の特徴はどんなことか。 【提问】这位作者认为&#xff0c;仕事能力强的人具有什么特点呢&#xff1f; 【11】 文章 下の文章は、企業のあり方について…...

【数据分享】2006-2021年我国城市级别的道路、桥梁、管线建设相关指标(10多项指标)

《中国城市建设统计年鉴》中细致地统计了我国城市市政公用设施建设与发展情况&#xff0c;在之前的文章中&#xff0c;我们分享过基于2006-2021年《中国城市建设统计年鉴》整理的2006—2021年我国城市级别的市政设施水平相关指标、2006-2021年我国城市级别的各类建设用地面积数…...

视觉SLAM14讲笔记-第7讲-视觉里程计2

直接法的引出 直接法是视觉里程计另一个主要分支&#xff0c;它与特征点法有很大的不同。 使用特征点法估计相机运动时&#xff0c;我们把特征点看作固定在三维空间的不动点。根据它们在相机中的投影位置&#xff0c;通过最小化重投影误差来优化相机运动。 相对地&#xff0c…...

MySQL——单行函数和分组函数

2023.9.3 单行函数的SQL语句学习笔记如下&#xff1a; #常见单行函数介绍&#xff08;部分省略&#xff09; #字符函数 #将姓变大写&#xff0c;名变小写&#xff0c;然后拼接。 SELECT CONCAT(UPPER(last_name), ,LOWER(first_name)) AS 姓名 FROM employees; # 姓名中首字符…...

百度百科词条怎么更新?怎么能顺利更新百科词条?

企业和个人百度百科词条的更新对于他们来说都具有重要的意义&#xff0c;具体如下&#xff1a; 对企业来说&#xff1a; 塑造品牌形象&#xff1a;百度百科是一个常被用户信任并参考的知识平台&#xff0c;通过更新企业词条可以提供准确、全面的企业信息&#xff0c;帮助企业塑…...

PPT怎么转换为PDF格式,收藏这两个在线工具。

PPT是一种常用的演示文稿格式&#xff0c;它可以包含丰富的动画效果和超链接&#xff0c;让你的内容更加生动和有趣。但是&#xff0c;如果你想将PPT分享给别人&#xff0c;或者在不同的设备上查看&#xff0c;你可能会遇到一些问题&#xff0c;比如&#xff1a; PPT文件太大&a…...

八大排序算法----堆排序

堆排序的基本步骤&#xff1a;&#xff08;以从大到小的顺序排序为例&#xff09; 1.构建大顶堆&#xff08;每个结点的值都大于或等于其左右孩子结点的值&#xff09; 2.排序&#xff1a;每次堆顶的元素取出来&#xff08;整个堆中值最大&#xff09;&#xff0c;与最后一个…...

Docker Desktop 设置镜像环境变量

点击run 展开Optional settings container name &#xff1a;容器名称 Ports&#xff1a;根据你需要的端口进行输入&#xff0c;不输入则默认 后面这个 比如我这个 5432 Volumes&#xff1a;卷&#xff0c;也就是做持久化 需要docker 数据保存的地方 Environment variables…...

springboot之一:配置文件(内外部配置优先顺序+properties、xml、yaml基础语法+profile动态切换配置、激活方式)

配置的概念&#xff1a; Spring Boot是基于约定的&#xff0c;所以很多配置都有默认值&#xff0c;但如果想使用自己的配置替换默认配置的话&#xff0c;就可以使用application.properties或者application.yml(application.yaml)进行配置。 注意配置文件的命名必须是applicat…...

涛然自得周刊(第 5 期):蝲蛄吟唱的地方

作者&#xff1a;何一涛 日期&#xff1a;2023 年 8 月 20 日 涛然自得周刊主要精选作者阅读过的书影音内容&#xff0c;不定期发。历史周刊内容可以看这里。 电影 《沼泽深处的女孩》 改编自小说《蝲蛄吟唱的地方》&#xff0c;主角是一位在沼泽地独自生活并长大的女孩&…...

Android Ble蓝牙App(七)扫描过滤

Ble蓝牙App&#xff08;七&#xff09;扫描过滤 前言目录正文一、增加菜单二、使用MMKV① 添加依赖② 封装MMKV③ 使用MMKV 三、过滤空设备名四、过滤Mac地址五、过滤RSSI六、源码 前言 在上一篇文章中了解了MTU的相关知识以及对于设备操作信息的展示&#xff0c;本篇文章中将增…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...