当前位置: 首页 > 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)进行数据回归预测的步骤如下: 数据准备:首先,将用于回归预…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

LangChain【6】之输出解析器:结构化LLM响应的关键工具

文章目录 一 LangChain输出解析器概述1.1 什么是输出解析器&#xff1f;1.2 主要功能与工作原理1.3 常用解析器类型 二 主要输出解析器类型2.1 Pydantic/Json输出解析器2.2 结构化输出解析器2.3 列表解析器2.4 日期解析器2.5 Json输出解析器2.6 xml输出解析器 三 高级使用技巧3…...

spring boot使用HttpServletResponse实现sse后端流式输出消息

1.以前只是看过SSE的相关文章&#xff0c;没有具体实践&#xff0c;这次接入AI大模型使用到了流式输出&#xff0c;涉及到给前端流式返回&#xff0c;所以记录一下。 2.resp要设置为text/event-stream resp.setContentType("text/event-stream"); resp.setCharacter…...

【汇编逆向系列】六、函数调用包含多个参数之多个整型-参数压栈顺序,rcx,rdx,r8,r9寄存器

从本章节开始&#xff0c;进入到函数有多个参数的情况&#xff0c;前面几个章节中介绍了整型和浮点型使用了不同的寄存器在进行函数传参&#xff0c;ECX是整型的第一个参数的寄存器&#xff0c;那么多个参数的情况下函数如何传参&#xff0c;下面展开介绍参数为整型时候的几种情…...

自定义线程池1.2

自定义线程池 1.2 1. 简介 上次我们实现了 1.1 版本&#xff0c;将线程池中的线程数量交给使用者决定&#xff0c;并且将线程的创建延迟到任务提交的时候&#xff0c;在本文中我们将对这个版本进行如下的优化&#xff1a; 在新建线程时交给线程一个任务。让线程在某种情况下…...

深入理解 C++ 左值右值、std::move 与函数重载中的参数传递

在 C 编程中&#xff0c;左值和右值的概念以及std::move的使用&#xff0c;常常让开发者感到困惑。特别是在函数重载场景下&#xff0c;如何合理利用这些特性来优化代码性能、确保语义正确&#xff0c;更是一个值得深入探讨的话题。 在开始之前&#xff0c;先提出几个问题&…...