当前位置: 首页 > 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 没有匹配…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...