leetcode_169. 多数元素
leetcode_169. 多数元素
问题描述
给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:nums = [3,2,3]
输出:3
示例 2:
输入:nums = [2,2,1,1,1,2,2]
输出:2
提示:
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109
**进阶:**尝试设计时间复杂度为 O ( n ) O(n) O(n)、空间复杂度为 O ( 1 ) O(1) O(1)的算法解决此问题。
题解-Boyer-Moore 投票算法
做这到题我们要紧扣两点, res(结果)一定是数组中最多的, 而且比其他任何数都多!!!
牢记上面的话, 然后我们来看算法
如果一场竞选中, 我们有 n n n个候选人, 每个候选人都会有自己的支持者, 对于第 i i i个候选人($ 0<=i<n ) 他们都有 )他们都有 )他们都有arr[i]$个支持者, 在竞选中, 每个支持者可以为自己支持的候选人投支持票, 同样也可以为自己不支持的候选人投反对票(每个人都只能有一个支持的候选人, 且每个人都能投一次票, 无论是支持还是反对). 这时, 有一个天降猛男**“甲”, 支持者超过了 50 % 50\% 50%, 那么请问, 如果其他候选者联合起来给甲"捣乱", 比如某几个候选人串通, 让他们的支持者去给甲**投反对票, 或者把票都投给某一个"甲"以外的候选者, 能不能对竞选结果产生影响呢?
显然不能, 因为甲的支持者是超过 50 % 50\% 50%的, 哪怕就超过一个人也是一样, 甲是 100 % 100\% 100% 会赢的, 无论其他人怎么操作. 就算剩下的所有的候选人支持者都把票投给一个人, 也不会超过甲.
在上面那个例子里, 甲就是我们的多数元素, 甲的支持者的数量就是多数元素出现的次数,
为了实现上面的算法, 我们需要维护两个变量, 一个res记录候选的多数元素和它出现的次数count, 一开始count为0, res记录数组的第一个元素, 随后每当遇到一个与当前res相同的 就执行count++, 否则就count--, 当count==0时, 就改变res的值为当前遍历的值,
这样一来, 无论数组里的元素顺序如何, 最后res里的值都会是我们的多数元素,
如果遍历到我们的多数元素时res中记录的正好是这个值, 那么count++, 就想当与支持者给自己投了支持票, 如果遍历到多数元素时, res中记录的是别的数字, 那么count--, 就相当于自己的支持者给别人投了反对票, 不管怎么样, 多数元素的票的总量多余其他所有元素之和, 所以最后res的值一定就是我们的多数元素.
java
class Solution {public int majorityElement(int[] nums) {int res = -1, count = 0;for (int num : nums) {if (count == 0) {res = num;count = 1;} else if (res == num ) {count ++;} else {count --;}}return res;}
}
C++
class Solution {
public:int majorityElement(vector<int>& nums) {int res = -1, count = 0;for (int num : nums) {if (count == 0) {res = num;count = 1;} else if (res == num ) {count ++;} else {count --;}}return res;}
};
相关文章:
leetcode_169. 多数元素
leetcode_169. 多数元素 问题描述 给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入:nums …...
STM32 GPIO的工作原理
STM32的GPIO管脚有下面8种可能的配置:(4输入 2 输出 2 复用输出) (1)浮空输入_IN_FLOATING 在上图上,阴影的部分处于不工作状态,尤其是下半部分的输出电路,实际上是与端口处于隔离状态。黄色的高亮部分显示…...
板级调试小助手(2)ZYNQ自定义IP核构建属于自己的DDS外设
一、前言 在上期文章中讲述了小助手的系统结构和原理。在PYNQ的框架开发中,我们一般可以将PL端当做PS端的一个外设,通过读写寄存器的方式来操作外设的功能,就类似于在开发ARM和DSP中操作外设一样,不同时的是,我们可以通…...
vim+cscope+ctags
一、简单安装 1.安装cscope # apt install cscope 2.安装ctags # apt install ctags 3.taglist安装 下载Vim source code browser plugin - Browse /vim-taglist at SourceForge.net,解压和复制文件 # unzip taglist_46.zip# cp doc/taglist.txt /usr/share/…...
Java 8的变革:函数式编程和Lambda表达式探索
文章目录 一、函数接口二、Lambda表达式简介三、Lambda表达式外部参数四、Lambda范例五、Runnable Lambda表达式 一、函数接口 函数接口是一个具有单个抽象方法的接口,接口设计主要是为了支持 Lambda 表达式和方法引用,使得 Java 能更方便地实现函数式编…...
Java集合框架的内部揭秘:List、Set与Map的深潜之旅
Java集合框架是一套强大的工具,为开发者提供了灵活的数据管理方式。本文将深入剖析List、Set和Map的内部机制,通过详细的示例和扩展讨论,带你领略这些数据容器的真谛。 一、List:有序序列的深度剖析 List接口是一个可以包含重复…...
爬虫(二)——爬虫的伪装
前言 本文是爬虫系列的第二篇文章,主要讲解关于爬虫的简单伪装,以及如何爬取B站的视频。建议先看完上一篇文章,再来看这一篇文章。要注意的是,本文介绍的方法只能爬取免费视频,会员视频是无法爬取的哦。 爬虫的伪装 …...
空安全编程的典范:Java 8中的安全应用指南
文章目录 一、Base64 编码解码1.1 基本的编码和解码1.2 URL 和文件名安全的编码解码器1.3 MIME Base64编码和解码 二、Optional类三、Nashorn JavaScript 一、Base64 编码解码 1.1 基本的编码和解码 Base64 编码: 使用 Base64.getEncoder().encodeToString(origin…...
Docker Machine 深入解析
Docker Machine 深入解析 引言 Docker Machine 是 Docker 生态系统中的一个重要工具,它简化了 Docker 容器环境的配置和管理过程。本文将深入探讨 Docker Machine 的概念、功能、使用场景以及如何在实际环境中高效利用它。 什么是 Docker Machine? Docker Machine 是一个…...
20.x86游戏实战-远线程注入的实现
免责声明:内容仅供学习参考,请合法利用知识,禁止进行违法犯罪活动! 本次游戏没法给 内容参考于:微尘网络安全 工具下载: 链接:https://pan.baidu.com/s/1rEEJnt85npn7N38Ai0_F2Q?pwd6tw3 提…...
06MFC之对话框--重绘元文件
文章目录 实现示例展示需要绘制的窗口/位置控件位置更新下一次示例粗细滑动部分更新重绘元文件(窗口变化内容消失)方法一:使用元文件方法二:兼容设备方法三:使用自定义类存储绘图数据除画笔外功能处理画笔功能处理保存前面画的线及色彩实现示例展示 需要绘制的窗口/位置 …...
鼠标的发明和鼠标“变形记”
注:机翻,未校对。 Who Invented the Computer Mouse? 谁发明了电脑鼠标? It was technology visionary and inventor Douglas Engelbart (January 30, 1925 – July 2, 2013) who revolutionized the way computers worked, turning it fr…...
快捷:通过胶水语言实现工作中测试流程并行、加速
通过胶水语言实现工作中测试流程并行、加速 通过胶水语言实现工作中测试流程并行、加速工作场景(背景)问题抽象(挑战)如何做(行动)获得了什么(结果)后记相关资源 通过胶水语言实现工…...
MySQL 和 PostgreSQL,我到底选择哪个?
MySQL 和 PostgreSQL 是两个广泛使用的关系型数据库管理系统(RDBMS)。它们都具有强大的功能和广泛的社区支持,但在某些方面存在一些差异。本文将详细比较 MySQL 和 PostgreSQL,包括它们的特点、性能、扩展性、安全性以及适用场景等…...
Java —— 内部类
Java内部类 1.什么是内部类? 将一个类A定义在另一个类B里面,里面的类A就称为内部类(InnerClass),类B则称为外部类(OuterClass)。 2.为什么需要内部类? 具体来说,当一…...
高职院校人工智能人才培养成果导向系统构建、实施要点与评量方法
一、引言 近年来,人工智能技术在全球范围内迅速发展,对各行各业产生了深远的影响。高职院校作为培养高技能人才的重要基地,肩负着培养人工智能领域专业人才的重任。为了适应社会对人工智能人才的需求,高职院校需要构建一套科学、…...
ffmpeg中的超时控制
在FFmpeg库中,很多函数没有直接的参数可以设置超时。 那么有哪些函数可以通过设置 AVFormatContext 的 interrupt_callback 来实现超时控制? avformat_open_input: 打开输入文件或流。这个函数会阻塞,尤其是在网络流的情况下&…...
搜维尔科技:【研究】触觉技术将在5年内以8种方式改变人们的世界
触觉技术在过去几年中发展迅猛,大大提高了反馈的精确度和真实度。其应用产生了真正的影响,数百家公司和企业都集成了触觉技术来增强培训和研究模拟。 虽然触觉技术主要用于 B2B 层面,但触觉技术可能会彻底改变我们的生活,尤其是通…...
项目收获总结--MyBatis的知识收获
MyBatis的知识收获 一、概述二、获取自动生成的(主)键值三、将sql执行结果封装为目标返回对象的方式和原理四、延迟加载实现原理五、批量插入六、自带分页与分页插件原理七、Mapper(Dao)接口与XML映射文件关系八、模糊查询like语句九、#{}和${}的区别十、二级缓存案例实战 一、…...
数据库管理-第221期 Oracle的高可用-04(20240717)
数据库管理221期 2024-07-17 数据库管理-第221期 Oracle的高可用-04(20240717)1 ADG2 连接配置2.1 TNS2.2 JDBC2.3 JAVA连接池2.3.1 Oracle UCP2.3.2 应用连接池基础配置 总结 数据库管理-第221期 Oracle的高可用-04(20240717) 作…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
Matlab实现任意伪彩色图像可视化显示
Matlab实现任意伪彩色图像可视化显示 1、灰度原始图像2、RGB彩色原始图像 在科研研究中,如何展示好看的实验结果图像非常重要!!! 1、灰度原始图像 灰度图像每个像素点只有一个数值,代表该点的亮度(或…...
6.9-QT模拟计算器
源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...
