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

(数学) 剑指 Offer 39. 数组中出现次数超过一半的数字 ——【Leetcode每日一题】

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

难度:简单

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

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

示例 1:

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

限制

  • 1 <= 数组长度 <= 50000

注意:本题 169. 多数元素 相同。

💡思路:投票问题

多数投票问题,可以利用 Boyer-Moore Majority Vote Algorithm 来解决这个问题,使得时间复杂度为 O ( n ) O(n) O(n)

使用 cnt 来统计一个元素出现的次数:

  • 当遍历到的元素和统计元素相等时,令 cnt++,否则令 cnt--
  • 如果前面查找了 i 个元素,且 cnt == 0,说明前 i 个元素没有 ans,或者有 ans,但是出现的次数少于 i / 2 ,因为如果多于 i / 2 的话 cnt 就一定不会为 0 。此时剩下的 n - i 个元素中,ans 的数目依然多于 (n - i) / 2,因此继续查找就能找出 ans

🍁代码:(C++、Java)

C++

class Solution {
public:int majorityElement(vector<int>& nums) {int ans = nums[0], cnt = 0;for(int num : nums) {ans  = cnt == 0 ? num : ans;cnt = ans == num ? ++cnt : --cnt;}return ans;}
};

Java

class Solution {public int majorityElement(int[] nums) {int ans = nums[0], cnt = 0;for(int num : nums) {ans  = cnt == 0 ? num : ans;cnt = ans == num ? ++cnt : --cnt;}return ans;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为数组的长度,Boyer-Moore 算法只对数组进行了一次遍历。。
  • 空间复杂度 O ( 1 ) O(1) O(1),只需要常数级别的额外空间。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!

相关文章:

(数学) 剑指 Offer 39. 数组中出现次数超过一半的数字 ——【Leetcode每日一题】

❓ 剑指 Offer 39. 数组中出现次数超过一半的数字 难度&#xff1a;简单 数组中有一个数字出现的次数超过数组长度的一半&#xff0c;请找出这个数字。 你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输…...

如何用PS把roughness贴图转换成Smoothness,并放入Metallic贴图的a通道。

1&#xff1a;用PS打开Roughness贴图 2&#xff1a;选择反相&#xff0c;装换成Smoothness贴图 3&#xff1a;新建一个大小相等的psd文件&#xff0c;或者打开Metallic贴图 4&#xff1a;如果没有金属度贴图&#xff0c;就把新建的图画成纯黑色 5&#xff1a;选择图层蒙版->…...

了解XSS攻击与CSRF攻击

什么是XSS攻击 XSS&#xff08;Cross-Site Scripting&#xff0c;跨站脚本攻击&#xff09;是一种常见的网络安全漏洞&#xff0c;它允许攻击者在受害者的浏览器上执行恶意脚本。这种攻击通常发生在 web 应用程序中&#xff0c;攻击者通过注入恶意脚本来利用用户对网站的信任&…...

安全测试-django防御安全策略

django安全性 django针对安全方面有一些处理&#xff0c;学习如何进行处理设置&#xff0c;也有利于学习安全测试知识。 CSRF 跨站点请求伪造&#xff08;Cross-Site Request Forgery&#xff0c;CSRF&#xff09;是一种网络攻击方式&#xff0c;攻击者欺骗用户在自己访问的网…...

7.react useReducer使用与常见问题

useReducer函数 1. useState的替代方案.接收一个(state, action)>newState的reducer, 并返回当前的state以及与其配套的dispatch方法2. 在某些场景下,useReducer会比useState更加适用,例如state逻辑较为复杂, 且**包含多个子值**,或者下一个state依赖于之前的state等清楚us…...

c#泛型(generic)

概述&#xff1a; C#中的泛型&#xff08;Generics&#xff09;是一种允许在编写类、方法和委托时使用参数化类型的机制。泛型允许我们编写更通用、可重用的代码&#xff0c;可以避免类型转换和重复编写类似的代码。 泛型的基本语法如下所示&#xff1a; class ClassName<…...

【力扣每日一题】2023.8.30 到家的最少跳跃次数

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 题目给我们一只跳蚤&#xff0c;我们可以操控它前跳 a 格或是后跳 b 格&#xff0c;不能跳到小于0的位置&#xff0c;有一些被禁止的点不…...

精读《算法题 - 地下城游戏》

今天我们看一道 leetcode hard 难度题目&#xff1a;地下城游戏。 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里&#xff0c;他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士…...

随记-Kibana Dev Tools,ES 增删改查 索引,Document

索引 创建索引 创建索引 PUT index_test创建索引 并 修改分片信息 # 创建索引 并 修改分片信息 PUT index_test2 { # 必须换行, PUT XXX 必须独占一行&#xff0c;类似的 其他请求也需要独占一行 "settings": {"number_of_shards": 1, # 主分片"…...

什么是架构,架构的本质是什么

不论是开发人员还是架构师&#xff0c;我们都一直在跟软件系统打交道&#xff0c;架构是在工作中出现最频繁的术语之一。那么&#xff0c;到底什么是架构&#xff1f;你可能有自己的答案&#xff0c;也有可能没有答案。对“架构”的理解需要我们不断在实践中思考、归纳、演绎&a…...

Python爬虫(十七)_糗事百科案例

糗事百科实例 爬取糗事百科段子&#xff0c;假设页面的URL是: http://www.qiushibaike.com/8hr/page/1 要求&#xff1a; 使用requests获取页面信息&#xff0c;用XPath/re做数据提取获取每个帖子里的用户头像连接、用户姓名、段子内容、点赞次数和评论次数保存到json文件内…...

Ae 效果:CC Threads

生成/CC Threads Generate/CC Threads CC Threads&#xff08;CC 编织条&#xff09;效果基于当前图层像素生成编织条图案和纹理。可以用在各种设计中&#xff0c;如背景设计、图形设计、文字设计等。 ◆ ◆ ◆ 效果属性说明 Width 宽度 设置编织的宽度。 默认值为 50。值越大…...

Kotlin 协程 - 多路复用 select()

一、概念 又叫选择表达式&#xff0c;是一个挂起函数&#xff0c;可以同时等待多个挂起结果&#xff0c;只取用最快恢复的那个值&#xff08;即多种方式获取数据&#xff0c;哪个更快返回结果就用哪个&#xff09;。 同时到达 select() 会优先选择先写子表达式&#xff0c;想随…...

学习笔记-ThreadLocal

ThreadLocal 什么是ThreadLocal&#xff1f; ThreadLocal 是线程本地变量类&#xff0c;在多线程并行执行过程中&#xff0c;将变量存储在ThreadLocal中&#xff0c;每个线程中都有独立的变量&#xff0c;因此不会出现线程安全问题。 应用举例 解决线程安全问题&#xff1a;例…...

python利用pandas统计分析—groupby()函数的使用

文章目录 一、groupby使用场景二、groupby基本原理三、groupby分组运算基础聚合操作&#xff1a;只能选择一种聚合操作agg 聚合操作&#xff1a;可以针对同列选择不同聚合方法transformapply 四、groupby分组后去重统计nunique()五、groupby分组后重命名列名rename()直接重新命…...

OPENCV实现ORB特征检测

# -*- coding:utf-8 -*- """ 作者:794919561 日期:2023/8/31 """ import cv2 import numpy as np# 读图像 img = cv2.imread(F:\\learnOpenCV\\openCVLearning\\pictures\\chess.jpg)...

W5100S-EVB-PICO主动PING主机IP检测连通性(十)

前言 上一章节我们用我们开发板在UDP组播模式下进行数据回环测试&#xff0c;本章我们用开发板去主动ping主机IP地址来检测与该主机之间网络的连通性。 什么是PING&#xff1f; PING是一种命令&#xff0c; 是用来探测主机到主机之间是否可通信&#xff0c;如果不能ping到某台…...

使用 Nginx 搭建文件下载服务器

文章目录 一、基础环境二、适用场景三、方法和步骤四、其他说明 版权声明&#xff1a;本文为CSDN博主「杨群」的原创文章&#xff0c;遵循 CC 4.0 BY-SA版权协议&#xff0c;于2023年8月27日首发于CSDN&#xff0c;转载请附上原文出处链接及本声明。 原文链接&#xff1a;http…...

链式栈StackT

C关键词&#xff1a;内部类/模板类/头插 C自学精简教程 目录(必读) C数据结构与算法实现&#xff08;目录&#xff09; 栈的内存结构 空栈&#xff1a; 有一个元素的栈&#xff1a; 多个元素的栈&#xff1a; 成员函数说明 0 clear 清空栈 clear 函数负责将栈的对内存释放…...

Fiddler中 AutoResponder 使用

Fiddler的 AutoResponder &#xff0c;即URL重定向功能非常强大。不管我们做URL重定向&#xff0c;还是做mock测试等&#xff0c;都可以通过该功能进行实践。 下面&#xff0c;小酋就来具体讲下该功能的用法。 Enable rules 启用规则Unmatched requests passthrough 没有匹配…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

Vue ③-生命周期 || 脚手架

生命周期 思考&#xff1a;什么时候可以发送初始化渲染请求&#xff1f;&#xff08;越早越好&#xff09; 什么时候可以开始操作dom&#xff1f;&#xff08;至少dom得渲染出来&#xff09; Vue生命周期&#xff1a; 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...