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

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.length
  • 1 <= 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 &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。 示例 1&#xff1a; 输入&#xff1a;nums …...

STM32 GPIO的工作原理

STM32的GPIO管脚有下面8种可能的配置:&#xff08;4输入 2 输出 2 复用输出) &#xff08;1&#xff09;浮空输入_IN_FLOATING 在上图上&#xff0c;阴影的部分处于不工作状态&#xff0c;尤其是下半部分的输出电路&#xff0c;实际上是与端口处于隔离状态。黄色的高亮部分显示…...

板级调试小助手(2)ZYNQ自定义IP核构建属于自己的DDS外设

一、前言 在上期文章中讲述了小助手的系统结构和原理。在PYNQ的框架开发中&#xff0c;我们一般可以将PL端当做PS端的一个外设&#xff0c;通过读写寄存器的方式来操作外设的功能&#xff0c;就类似于在开发ARM和DSP中操作外设一样&#xff0c;不同时的是&#xff0c;我们可以通…...

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&#xff0c;解压和复制文件 # unzip taglist_46.zip# cp doc/taglist.txt /usr/share/…...

Java 8的变革:函数式编程和Lambda表达式探索

文章目录 一、函数接口二、Lambda表达式简介三、Lambda表达式外部参数四、Lambda范例五、Runnable Lambda表达式 一、函数接口 函数接口是一个具有单个抽象方法的接口&#xff0c;接口设计主要是为了支持 Lambda 表达式和方法引用&#xff0c;使得 Java 能更方便地实现函数式编…...

Java集合框架的内部揭秘:List、Set与Map的深潜之旅

Java集合框架是一套强大的工具&#xff0c;为开发者提供了灵活的数据管理方式。本文将深入剖析List、Set和Map的内部机制&#xff0c;通过详细的示例和扩展讨论&#xff0c;带你领略这些数据容器的真谛。 一、List&#xff1a;有序序列的深度剖析 List接口是一个可以包含重复…...

爬虫(二)——爬虫的伪装

前言 本文是爬虫系列的第二篇文章&#xff0c;主要讲解关于爬虫的简单伪装&#xff0c;以及如何爬取B站的视频。建议先看完上一篇文章&#xff0c;再来看这一篇文章。要注意的是&#xff0c;本文介绍的方法只能爬取免费视频&#xff0c;会员视频是无法爬取的哦。 爬虫的伪装 …...

空安全编程的典范:Java 8中的安全应用指南

文章目录 一、Base64 编码解码1.1 基本的编码和解码1.2 URL 和文件名安全的编码解码器1.3 MIME Base64编码和解码 二、Optional类三、Nashorn JavaScript 一、Base64 编码解码 1.1 基本的编码和解码 Base64 编码&#xff1a; 使用 Base64.getEncoder().encodeToString(origin…...

Docker Machine 深入解析

Docker Machine 深入解析 引言 Docker Machine 是 Docker 生态系统中的一个重要工具,它简化了 Docker 容器环境的配置和管理过程。本文将深入探讨 Docker Machine 的概念、功能、使用场景以及如何在实际环境中高效利用它。 什么是 Docker Machine? Docker Machine 是一个…...

20.x86游戏实战-远线程注入的实现

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 本次游戏没法给 内容参考于&#xff1a;微尘网络安全 工具下载&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1rEEJnt85npn7N38Ai0_F2Q?pwd6tw3 提…...

06MFC之对话框--重绘元文件

文章目录 实现示例展示需要绘制的窗口/位置控件位置更新下一次示例粗细滑动部分更新重绘元文件(窗口变化内容消失)方法一:使用元文件方法二:兼容设备方法三:使用自定义类存储绘图数据除画笔外功能处理画笔功能处理保存前面画的线及色彩实现示例展示 需要绘制的窗口/位置 …...

鼠标的发明和鼠标“变形记”

注&#xff1a;机翻&#xff0c;未校对。 Who Invented the Computer Mouse? 谁发明了电脑鼠标&#xff1f; It was technology visionary and inventor Douglas Engelbart (January 30, 1925 – July 2, 2013) who revolutionized the way computers worked, turning it fr…...

快捷:通过胶水语言实现工作中测试流程并行、加速

通过胶水语言实现工作中测试流程并行、加速 通过胶水语言实现工作中测试流程并行、加速工作场景&#xff08;背景&#xff09;问题抽象&#xff08;挑战&#xff09;如何做&#xff08;行动&#xff09;获得了什么&#xff08;结果&#xff09;后记相关资源 通过胶水语言实现工…...

MySQL 和 PostgreSQL,我到底选择哪个?

MySQL 和 PostgreSQL 是两个广泛使用的关系型数据库管理系统&#xff08;RDBMS&#xff09;。它们都具有强大的功能和广泛的社区支持&#xff0c;但在某些方面存在一些差异。本文将详细比较 MySQL 和 PostgreSQL&#xff0c;包括它们的特点、性能、扩展性、安全性以及适用场景等…...

Java —— 内部类

Java内部类 1.什么是内部类&#xff1f; 将一个类A定义在另一个类B里面&#xff0c;里面的类A就称为内部类&#xff08;InnerClass&#xff09;&#xff0c;类B则称为外部类&#xff08;OuterClass&#xff09;。 2.为什么需要内部类&#xff1f; 具体来说&#xff0c;当一…...

高职院校人工智能人才培养成果导向系统构建、实施要点与评量方法

一、引言 近年来&#xff0c;人工智能技术在全球范围内迅速发展&#xff0c;对各行各业产生了深远的影响。高职院校作为培养高技能人才的重要基地&#xff0c;肩负着培养人工智能领域专业人才的重任。为了适应社会对人工智能人才的需求&#xff0c;高职院校需要构建一套科学、…...

ffmpeg中的超时控制

在FFmpeg库中&#xff0c;很多函数没有直接的参数可以设置超时。 那么有哪些函数可以通过设置 AVFormatContext 的 interrupt_callback 来实现超时控制&#xff1f; avformat_open_input&#xff1a; 打开输入文件或流。这个函数会阻塞&#xff0c;尤其是在网络流的情况下&…...

搜维尔科技:【研究】触觉技术将在5年内以8种方式改变人们的世界

触觉技术在过去几年中发展迅猛&#xff0c;大大提高了反馈的精确度和真实度。其应用产生了真正的影响&#xff0c;数百家公司和企业都集成了触觉技术来增强培训和研究模拟。 虽然触觉技术主要用于 B2B 层面&#xff0c;但触觉技术可能会彻底改变我们的生活&#xff0c;尤其是通…...

项目收获总结--MyBatis的知识收获

MyBatis的知识收获 一、概述二、获取自动生成的(主)键值三、将sql执行结果封装为目标返回对象的方式和原理四、延迟加载实现原理五、批量插入六、自带分页与分页插件原理七、Mapper(Dao)接口与XML映射文件关系八、模糊查询like语句九、#{}和${}的区别十、二级缓存案例实战 一、…...

数据库管理-第221期 Oracle的高可用-04(20240717)

数据库管理221期 2024-07-17 数据库管理-第221期 Oracle的高可用-04&#xff08;20240717&#xff09;1 ADG2 连接配置2.1 TNS2.2 JDBC2.3 JAVA连接池2.3.1 Oracle UCP2.3.2 应用连接池基础配置 总结 数据库管理-第221期 Oracle的高可用-04&#xff08;20240717&#xff09; 作…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

WebRTC调研

WebRTC是什么&#xff0c;为什么&#xff0c;如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究

摘要&#xff1a;在消费市场竞争日益激烈的当下&#xff0c;传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序&#xff0c;探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式&#xff0c;分析沉浸式体验的优势与价值…...

算法—栈系列

一&#xff1a;删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...