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

leetcode经典面试150题---5.多数元素

目录

题目描述

前置知识

代码

方法一 排序法

思路

实现

复杂度

方法二 哈希表

思路

实现


题目描述


给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

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

示例 1:

输入:nums = [3,2,3]
输出:3

示例 2:

输入:nums = [2,2,1,1,1,2,2]
输出:2

前置知识


  • 哈希表

代码


方法一 排序法

思路

如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序,那么下标为(n/2)的元素(下标从 0 开始)一定是多数

实现

class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];}
}

复杂度

  • 时间复杂度:O(nlogn)。将数组排序的时间复杂度为 O(nlog⁡n)
  • 空间复杂度:O(log⁡n)

方法二 哈希表

思路

  • 我们知道出现次数最多的元素大于 2/n次,所以可以用哈希表来快速统计每个元素出现的次数。

实现

class Solution {private Map<Integer, Integer> countNums(int[] nums) {Map<Integer, Integer> counts = new HashMap<Integer, Integer>();for (int num : nums) {if (!counts.containsKey(num)) {counts.put(num, 1);} else {counts.put(num, counts.get(num) + 1);}}return counts;}public int majorityElement(int[] nums) {Map<Integer, Integer> counts = countNums(nums);Map.Entry<Integer, Integer> majorityEntry = null;for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {majorityEntry = entry;}}return majorityEntry.getKey();}
}

复杂度

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

相关文章:

leetcode经典面试150题---5.多数元素

目录 题目描述 前置知识 代码 方法一 排序法 思路 实现 复杂度 方法二 哈希表 思路 实现 题目描述 给定一个大小为 n 的数组 nums &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的&#xff0c;并且给…...

Vue ElementUI el-tooltip 全局样式修改

el-tooltip 要点 此处是全局配置&#xff1b;如果想设置指定的 tooltip 可设置属性 popper-class&#xff0c;为 tooltip 的 popper 添加类名&#xff1b;代码 6 - 8 行&#xff0c;隐藏小三角&#xff1b; .el-tooltip__popper {border-radius: 4px !important;color: #9E9…...

MATLAB_5MW风电永磁直驱发电机-1200V直流并网MATLAB仿真模型

仿真软件&#xff1a;matlab2016b 风机传动模块、PMSG模块、蓄电池模块、超级电容模块、无穷大电源、蓄电池控制、风机控制、逆变器控制等模块。 逆变器输出电压&#xff1a; 混合储能系统SOC&#xff1a; 威♥关注“电击小子程高兴的MATLAB小屋”获取更多精彩资料&#xff0…...

11.4商业伦理(全)

大型工商业城市和小城市的商业伦理道德水平是否存在差异&#xff0c;如果有&#xff0c;存在哪些差异&#xff1f; 伦理道德对产业分工的影响 产业层级越高&#xff0c;需要的商业伦理道德水平越高 产业级别越高&#xff0c;利润率越高 去中心化的去信任化的比特币会不会取…...

【漏洞复现】S2-045 Remote Code Execution(CVE-2017-5638)

感谢互联网提供分享知识与智慧&#xff0c;在法治的社会里&#xff0c;请遵守有关法律法规 文章目录 1.1、漏洞描述1.2、漏洞等级1.3、影响版本1.4、漏洞复现1、基础环境2、漏洞扫描nacs3、漏洞验证 1.5、修复建议 说明内容漏洞编号CVE-2017-5638漏洞名称S2-045 远程代码执行漏…...

Linux----------------Shell重定向输入输出

&#xff08;一&#xff09; 标准输入 以键盘读取用户输入的数据&#xff0c;然后再把数据拿到 Shel程序中使用。 标准输出 Shell 程序产生的数据&#xff0c;这些数据一般都是呈现到显示器上供用户浏览查看 输入输出重定向 输入方向就是数据从哪里流向程序。数据默认从键…...

apachesolr中简单使用

core使用 首先点击add core 可以看到报错solrconfig.xml不在new_core目录下&#xff0c;new_core是我们点击后自动创建的 那么我们将D:\solr2\solr-9.3.0\solr-9.3.0\server\solr\configsets下的任何一个目录下的conf拷贝到new_core过去 这里是使用_default下的conf目录拷贝…...

C++多线程编程:其一、thread类概述

thread是C11版本中出现的线程对象&#xff0c;可以让程序员非常方便地创建线程。 非空的thread对象创建以后&#xff0c;线程就会自动运行起来。简单地理解&#xff0c;一个线程对象中会传入一个函数指针&#xff0c;之后编译器会构造一个栈&#xff0c;将这个函数指针压栈。函…...

C++11 initializer_list 轻量级初始化列表的使用场景(让自定义类可以用初始化列表的形式来实例化对象)

initializer_list 是 C11 中的一个特性&#xff0c;它允许你使用花括号 {} 中的值列表来初始化容器或数组。通常用于初始化标准库容器&#xff0c;比如 std::vector、std::set、std::map 以及数组。 场景一&#xff1a;用初始化列表初始化容器 std::vector<int> arr {…...

请求地址‘/operlog‘,发生未知异常

&#x1f468;&#x1f3fb;‍&#x1f4bb; 热爱摄影的程序员 &#x1f468;&#x1f3fb;‍&#x1f3a8; 喜欢编码的设计师 &#x1f9d5;&#x1f3fb; 擅长设计的剪辑师 &#x1f9d1;&#x1f3fb;‍&#x1f3eb; 一位高冷无情的编码爱好者 大家好&#xff0c;我是全栈工…...

Makefile 保姆级使用教程

目录 Makefile 规则 Makefile的使用介绍 make 命令的使用 即时变量、延时变量介绍和使用 使用make命令编译多个文件 假想目标 常用函数 1.$(foreach var,list,text) 2.$(wildcard pattern) 3.$(filter pattern...,text) 4.$(filter-out pattern...,text) 5.$(patsub…...

【GitHub】Watch、Star、Fork、Follow 有什么区别?

目录 一、前言二、区别1. Watch2. Star3. Fork4. Follow 一、前言 GitHub 是最受欢迎的代码托管平台之一&#xff0c;拥有大量的开源代码可供学习。 Github 中也有类似 “点赞”、“收藏”、“加关注” 的功能。 下面介绍下&#xff0c;GitHub 中 Watch、Star、Fork、Follow 有…...

MyBatis实现多表映射、分页显示、逆向工程

目录 一、MyBatis实现多表映射 1.1 实体类设计 1.2 一对一关系实现案例 1.3 对多配置实现案例 1.4 设置自动映射与n张表关联映射 二、MyBatis实现分页功能 2.1 mybatis插件工作原理 2.2 引入插件与插件的使用 三、逆向工程插件 3.1 什么是逆向工程 3.2 MyBat…...

C++基础面试题

一、vector和list的区别 1.1 底层数据结构 vector 使用动态数组作为底层数据结构&#xff0c;元素在内存中是连续存储的&#xff1b; list 使用双向链表作为底层数据结构&#xff0c;元素在内存中通过节点相互连接。 1.2 插入和删除操作 vector 在尾部插入或删除元素效率高&…...

asp.net人事管理信息系统VS开发sqlserver数据库web结构c#编程Microsoft Visual Studio

一、源码特点 asp.net 人事管理信息系统是一套完善的web设计管理系统&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为vs2010&#xff0c;数据库为sqlserver2008&#xff0c;使用c#语言 开发 asp.net 人事管理系统1 应用技术…...

【Docker】Docker中 的AUFS、BTRFS、ZFS、存储池概念的详细讲解

前言 作者简介&#xff1a; 辭七七&#xff0c;目前大二&#xff0c;正在学习C/C&#xff0c;Java&#xff0c;Python等 作者主页&#xff1a; 七七的个人主页 文章收录专栏&#xff1a; 七七的闲谈 欢迎大家点赞 &#x1f44d; 收藏 ⭐ 加关注哦&#xff01;&#x1f496;&…...

华为云运维小结

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、pandas是什么&#xff1f; 一、pandas是什么&#xff1f; HCIP学习笔记-华为云运维方案-9&#xff1a;https://blog.csdn.net/GoNewWay/article/details/13152…...

Firefox 119 正式发布

Firefox 119 已正式发布。新版本除了修复 Bug 之外&#xff0c;还增强了 Firefox View 功能、支持在 PDF 文档中插入图片&#xff0c;以及引入 Encrypted Client Hello (ECH) 以增强隐私保护等。 主要变化 改进 Firefox View&#xff1a;用户可以在该页面查看所有窗口打开的标…...

apachesolr启动带调试

这里solr.cmd报错&#xff0c;报错原因是java版本问题&#xff0c;后面发现这是因为多个java版本导致读取java_home失败&#xff0c; 那么我们修改solr.cmd中的JAVA_HOME为SOLR_JAVA_HOME IF DEFINED SOLR_JAVA_HOME set "JAVA_HOME%SOLR_JAVA_HOME%"环境变量将SOLR…...

【MATLAB】基于灰狼优化算法优化BP神经网络 (GWO-BP)的数据回归预测

文章目录 效果一览文章概述订阅专栏只能获取一份代码部分源码参考资料效果一览 文章概述 【MATLAB】基于灰狼优化算法优化BP神经网络 (GWO-BP)的数据回归预测 在MATLAB中,基于灰狼优化算法优化BP神经网络(GWO-BP)进行数据回归预测的步骤如下: 数据准备:首先,将用于回归预…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

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

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

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...