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

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

python数据结构和算法(1)

数据结构和算法简介 数据结构&#xff1a;存储和组织数据的方式&#xff0c;决定了数据的存储方式和访问方式。 算法&#xff1a;解决问题的思维、步骤和方法。 程序 数据结构 算法 算法 算法的独立性 算法是独立存在的一种解决问题的方法和思想&#xff0c;对于算法而言&a…...