当前位置: 首页 > 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;本篇文章中将增…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...