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

剑指 Offer 39. 数组中出现次数超过一半的数字

剑指 Offer 39. 数组中出现次数超过一半的数字

难度:easy\color{Green}{easy}easy


题目描述

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

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

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制:

1<=数组长度<=500001 <= 数组长度 <= 500001<=数组长度<=50000

注意:本题与主站 169 题相同:https://leetcode-cn.com/problems/majority-element/

  • 腾讯视频后端的算法题,要求空间复杂度为 O(1)O(1)O(1)

算法

(摩尔投票法)

设输入数组 nums 的众数为 x ,数组长度为 n

  • 推论一: 若记 众数 的票数为 +1 ,非众数 的票数为 −1 ,则一定有所有数字的 票数和 >0

  • 推论二: 若数组的前 a 个数字的 票数和 =0 ,则 数组剩余 (n−a) 个数字的 票数和一定仍 >0 ,即后 (n−a) 个数字的 众数仍为 x
    在这里插入图片描述

算法流程:

  • 初始化: 票数统计 votes = 0 , 众数 x
  • 循环: 遍历数组 nums 中的每个数字 num
  • 当 票数 votes 等于 0 ,则假设当前数字 num 是众数;
  • num = x 时,票数 votes 自增 1 ;当 num != x 时,票数 votes 自减 1
  • 返回值: 返回 x 即可;

复杂度分析

  • 时间复杂度O(n)O(n)O(n),其中 nnn 是数组的长度。

  • 空间复杂度 : O(1)O(1)O(1),只需要 vote 常量

C++ 代码

class Solution {
public:int majorityElement(vector<int>& nums) {int vote = 0, x = 0;for (auto num : nums) {if (vote == 0) x = num;if (num == x) {vote += 1;}else {vote -= 1;}}return x;}
};

相关文章:

剑指 Offer 39. 数组中出现次数超过一半的数字

剑指 Offer 39. 数组中出现次数超过一半的数字 难度&#xff1a;easy\color{Green}{easy}easy 题目描述 数组中有一个数字出现的次数超过数组长度的一半&#xff0c;请找出这个数字。 你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。 示例 1: 输入: …...

使用python控制摄像头

前言 当今&#xff0c;随着计算机技术的发展&#xff0c;摄像头已经成为了人们生活中不可或缺的一部分。而Python作为一种流行的编程语言&#xff0c;也可以轻松地控制和操作摄像头。无论你是想用Python写一个简单的摄像头应用程序&#xff0c;还是想在机器学习和计算机视觉项…...

Linux文件系统

目录 1、常见的linux文件系统 2、文件系统的组成 inode的内容&#xff1a; 可以用stat命令&#xff0c;查看某个文件的inode信息 inode的大小 inode号码 使用 ls -i来查看文件的inode号码 使用 df -i命令&#xff0c;查看每个硬盘分区的inode总数和已经使用的数量&#xff…...

扬帆优配|引活水 增活力 促转型 创业板助力实体经济高质量发展

立异就是生产力&#xff0c;企业赖之以强&#xff0c;国家赖之以盛。全面注册制变革持续开释立异生机。日前&#xff0c;创业板公司已开端连续公布2022年度年度报告和2023年第一季度成绩预告&#xff0c;从频频传来的“喜报”中可窥见立异驱动开展战略下新兴工业的强劲开展态势…...

【c++】:STL模板中string的使用

文章目录 STL简介一.认识string二.string中基本功能的使用总结STL简介 STL(standard template libaray-标准模板库)&#xff1a;是C标准库的重要组成部分&#xff0c;不仅是一个可复用的组件库&#xff0c;而且是一个包罗数据结构与算法的软件框架。STL的版本 原始版本 Alexand…...

华为OD机试用Python实现 -【连续字母长度 or 求第 K 长的字符串长度】 | 2023.Q1 A卷

华为OD机试题 本篇题目:连续字母长度 or 求第 K 长的字符串长度题目输入描述输出描述示例一输入输出说明示例二输入输出说明示例三输入输出说明Code代码编写逻辑最近更新的博客 华为od 2023 | 什么是华为od,od...

前端处理并发的最佳实践

什么是并发&#xff1f; 因为js是单线程的&#xff0c;所以前端的并发指的是在极短时间内发送多个数据请求&#xff0c;比如说循环中发送ajax。 举一个简单的例子&#xff1a; 下面一段代码是常规的mount阶段执行的请求&#xff1a; useEffect(async () > {console.time…...

【SOP 】配电网故障重构方法研究【IEEE33节点】(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

[MySQL索引]4.索引的底层原理(三)

索引的底层原理&#xff08;三&#xff09;哈希索引InnoDB自适应哈希索引哈希索引 memory存储引擎支持的是哈希索引&#xff0c;memory是支持内存的存储引擎。 哈希表中的元素没有任何顺序可言&#xff0c;只能进行等值比较&#xff0c;包括范围搜索、前缀搜索like、order by…...

2023金三银四应届生求职面试指南

一、应届生优势 划重点&#xff0c;一定要走校招;千万不要等毕业之后再想着找工作&#xff0c;在毕业前就要敲定落实;否则&#xff0c;就真的该焦虑了。要知道应届生的身份是一个很吃香的身份;只有应届生可以走校园招聘。 1、那校园招聘跟社会招聘有多大的差距?? 这么说吧&…...

【数据结构】解决顺序表题的基本方法

&#x1f680;write in front&#x1f680; &#x1f4dc;所属专栏&#xff1a;> 初阶数据结构 &#x1f6f0;️博客主页&#xff1a;睿睿的博客主页 &#x1f6f0;️代码仓库&#xff1a;&#x1f389;VS2022_C语言仓库 &#x1f3a1;您的点赞、关注、收藏、评论&#xff0…...

HDFS如何解决海量数据存储及解决方案详解

HDFS组件 HDFS组件的基准测试 说明 一般在搭建完集群之后&#xff0c;运维人员需要对集群进行压力测试&#xff0c;对于HDFS来讲&#xff0c;主要是读写测试写入测试 hadoop jar /export/server/hadoop-3.3.0/share/hadoop/mapreduce/hadoop-mapreduce-client-jobclient-3.…...

认识CSS值如何提高写前端代码的效率

&#x1f31f;所属专栏&#xff1a;前端只因变凤凰之路&#x1f414;作者简介&#xff1a;rchjr——五带信管菜只因一枚&#x1f62e;前言&#xff1a;该系列将持续更新前端的相关学习笔记&#xff0c;欢迎和我一样的小白订阅&#xff0c;一起学习共同进步~&#x1f449;文章简…...

MySQL知识点全面总结3:Mysql高级篇

三.MySQL知识点全面总结3&#xff1a;mysql高级篇 1.mysql语句的执行过程&#xff1f; 2.myesql事务详解&#xff1f; 3.mysql日志详解&#xff1f; 4.mysql的索引功能详解&#xff1f; 5.mysql的存储引擎详解&#xff1f; 6.mysql事务提交后数据与硬盘如何交互存储&…...

Spring注解开发之组件注册(二)

Spring注解开发之组件注册(一) 5.Import 给容器导入一个组件 给容器中注册组件 一、包扫描 组件标注注解&#xff08;Controller/Service/Repository/Component&#xff09; [自己写的类] 二、Bean [导入的第三包里面的组件] 三、Import [快速给容器中导入组件] (Import{…...

【web前端开发】CSS最常用的11种选择器

文章目录1.CSS介绍2.CSS的语言规则3.CSS的引入方式4.选择器标签选择器类选择器id选择器通配符选择器复合选择器后代选择器子代选择器并集选择器交集选择器伪类选择器hover伪类选择器active伪类选择器结构伪类选择器结语1.CSS介绍 CSS (Cascading Style Sheets&#xff0c;层叠样…...

微电影广告发展的痛点

微电影广告以不可阻挡之势进入大众生活中&#xff0c;企业利用微电影广告来进行企业形象塑造的例子比比皆是。于是乎&#xff0c;微电影广告在为企业塑造品牌形象方面上取得了可喜的效果&#xff0c;但也不可忽视&#xff0c;在这个发展过程中&#xff0c;微电影广告所面临的问…...

uniapp新手入门

前言&#xff1a; 这篇文章主要写的是uniapp的基础知识&#xff0c;可以让大家快速上手uniapp&#xff0c;同时避掉一些可能踩到的坑。 一. 什么是uniapp uniapp是由dcloud 公司开发的多端融合框架。uniapp的出现让我们的开发更为方便&#xff0c;一次开发&#xff0c;多端运行…...

linux segfault at 问题定位实践

问题&#xff1a;程序崩溃&#xff0c;打印为&#xff1a;app[13016]: segfault at 7fb668d29930 ip 00007fb668d3c23c sp 00007fb668e7de20 error 7 in mydefine.so[7fb668d3400011000]定位步骤&#xff1a;基础分析数据&#xff0c;大概了解反馈信息&#xff08;根据chatGPT&…...

SpringCloud+SpringCloudAlibaba

架构的演进1.1单体架构将所有业务场景的表示层、业务逻辑层和数据访问层放在一个工程中&#xff0c;最终经过编译、打包&#xff0c;部署在一台服务器上。◆ 1.1.1单体架构的优点1&#xff09;部署简单: 由于是完整的结构体&#xff0c;可以直接部署在一个服务器上即可。2&…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁

赛门铁克威胁猎手团队最新报告披露&#xff0c;数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据&#xff0c;严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能&#xff0c;但SEMR…...

Spring AOP代理对象生成原理

代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】&#xff0c;这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...

使用ch340继电器完成随机断电测试

前言 如图所示是市面上常见的OTA压测继电器&#xff0c;通过ch340串口模块完成对继电器的分路控制&#xff0c;这里我编写了一个脚本方便对4路继电器的控制&#xff0c;可以设置开启时间&#xff0c;关闭时间&#xff0c;复位等功能 软件界面 在设备管理器查看串口号后&…...

【threejs】每天一个小案例讲解:创建基本的3D场景

代码仓 GitHub - TiffanyHoo/three_practices: Learning three.js together! 可自行clone&#xff0c;无需安装依赖&#xff0c;直接liver-server运行/直接打开chapter01中的html文件 运行效果图 知识要点 核心三要素 场景&#xff08;Scene&#xff09; 使用 THREE.Scene(…...