首页/新闻资讯/正文详情

LeetCode 169. 多数元素:从排序到摩尔投票的三种解法

发布时间:2026/11/6 5:25:58 来源:云帆数科 栏目:资讯中心
LeetCode 169. 多数元素:从排序到摩尔投票的三种解法
题目描述给定一个大小为n的数组nums返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。示例输入nums [3, 2, 3] 输出3 输入nums [3, 3, 4] 输出3提示n nums.length1 n 5 * 10^4-10^9 nums[i] 10^9思路一排序取中位数由于多数元素出现的次数严格大于n/2所以把数组排序之后位于中间位置的元素一定是多数元素。这是最直观、代码最短的写法。class Solution: def majorityElement(self, nums: list[int]) - int: nums.sort() return nums[len(nums) // 2]复杂度分析时间复杂度O(n log n)主要开销在排序。空间复杂度O(log n)排序所需的栈空间原地排序。思路二哈希表计数遍历数组用字典记录每个元素出现的次数最后取出出现次数最多的那个元素。思路清晰适合作为通用解法。class Solution: def majorityElement(self, nums: list[int]) - int: count {} for num in nums: if num in count: count[num] 1 else: count[num] 1 return max(count, keycount.get)复杂度分析时间复杂度O(n)只需遍历一次数组。空间复杂度O(n)最坏情况下需要存储所有不同的元素。小提示变量名不要用dict它会覆盖 Python 内置的dict类型建议改成count或freq。思路三摩尔投票法最优解摩尔投票法的核心思想是“抵消”把多数元素记为1其他元素记为-1全部加起来一定大于 0。因此可以维护一个候选元素candidate和计数器count当count 0时说明之前的元素都被抵消完了把当前元素设为新的候选当前元素等于候选时count 1当前元素不等于候选时count - 1。遍历结束后剩下的候选元素就是多数元素。class Solution: def majorityElement(self, nums: list[int]) - int: # 摩尔投票 count 0 candidate None for num in nums: if count 0: candidate num count 1 elif num candidate: count 1 else: count - 1 return candidate复杂度分析时间复杂度O(n)只需遍历一次数组。空间复杂度O(1)只用了常数个变量。完整测试代码if __name__ __main__: print(Solution().majorityElement([3, 3, 4])) # 输出 3 print(Solution().majorityElement([3, 2, 3])) # 输出 3 print(Solution().majorityElement([1])) # 输出 1三种解法对比解法时间复杂度空间复杂度特点排序取中位数O(n log n)O(log n)代码最短依赖排序哈希表计数O(n)O(n)通用性强易理解摩尔投票法O(n)O(1)最优解面试常考总结本题的关键在于理解“多数元素出现次数大于n/2”这一条件带来的性质排序后中位数必为答案而摩尔投票法则利用元素之间的相互抵消在O(n)时间、O(1)空间内得到结果。实际面试中建议先说出哈希表思路再给出摩尔投票法作为优化体现对复杂度优化的思考过程。

相关推荐

空圈容错落进Python:用架构约束把R4焊死在CI里
空圈容错落进Python:用架构约束把R4焊死在CI里

定位:这不是一篇“Python架构最佳实践”,是用空圈容错理论的 R4(跨层跳步)和 R2(假异构)去诊断 Python 项目里“依赖方向悄悄焊反”的问题,并给出一个可落地的切入口——import-linter 的 layer… · 2026/11/6 5:24:58

如何在 Windows 11/10 中查找最近关闭的应用[内置 + 免费工具]
如何在 Windows 11/10 中查找最近关闭的应用[内置 + 免费工具]

快速答案 可以,你可以在 Windows 11 或 10 里查看最近关闭的应用,但也不完全是那么回事。不过,某种程度上你可以借可靠性监视器、事件查看器,或 NirSoft 的 LastActivityView 这类第三方工具做到。Windows 本身并不提供直接的“最近关闭的应用”历史记录;但这些方法能让你… · 2026/11/6 5:24:58

2026量化软件推荐 有统计基础的个人投资者怎么选
2026量化软件推荐 有统计基础的个人投资者怎么选

BigQuant、牛股王股票和米筐RQAlpha Plus,可以列入有统计基础的个人投资者的初步名单。愿意阅读数据表达并组织实验,可了解BigQuant;希望先在条件设置中明确投资假设,可查看牛股王股票;准备自己处理研究程序和结果表&a… · 2026/11/6 5:24:58

蓝奏云少点几下鼠标怎么做?Lanzou-Enhanced 油猴脚本使用指南
蓝奏云少点几下鼠标怎么做?Lanzou-Enhanced 油猴脚本使用指南

蓝奏云少点几下鼠标怎么做?Lanzou-Enhanced 油猴脚本使用指南 【免费下载链接】UserScript 🐵 自用的一些乱七八糟 油猴脚本~ 项目地址: https://gitcode.com/gh_mirrors/us/UserScript 在蓝奏云网盘后台管理文件时,有几个细节很磨人… · 2026/11/6 6:17:11

dsh-our-free-model 用量看板完全指南:Token、生成速度与首字延迟一次看懂
dsh-our-free-model 用量看板完全指南:Token、生成速度与首字延迟一次看懂

dsh-our-free-model 用量看板完全指南:Token、生成速度与首字延迟一次看懂 【免费下载链接】dsh-our-free-model 在 dsh 里装上这个插件即可,无需登录、注册或填 API Key,就能使用包括 DeepSeek V4.1 Flash、Kimi K3 在内的前沿模型——完全免… · 2026/11/6 6:17:11

通信概念--虚拟局域网(VLAN)
通信概念--虚拟局域网(VLAN)

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/6 6:17:11

palera1n 上手全解:A8–A11 老设备如何在 iOS 15+ 上恢复越狱?
palera1n 上手全解:A8–A11 老设备如何在 iOS 15+ 上恢复越狱?

palera1n 上手全解:A8–A11 老设备如何在 iOS 15 上恢复越狱? 【免费下载链接】palera1n Jailbreak for A8 through A11, T2 devices, on iOS/iPadOS/tvOS 15.0, bridgeOS 5.0 and higher. 项目地址: https://gitcode.com/GitHub_Trending/pa/palera1n… · 2026/11/6 6:17:11

11 组 Waves 预设一步到位:DiceBear 头像配色速查
11 组 Waves 预设一步到位:DiceBear 头像配色速查

11 组 Waves 预设一步到位:DiceBear 头像配色速查 【免费下载链接】dicebear DiceBear is an avatar library for designers and developers. 🌍 项目地址: https://gitcode.com/gh_mirrors/di/dicebear 想给产品里一排头像统一换暖色调&#xff… · 2026/11/6 6:17:11

C语言:作用域、链接与存储期
C语言:作用域、链接与存储期

相关阅读 C语言https://blog.csdn.net/weixin_45791458/category_12423166.html?spm1001.2014.3001.5482 目录 作用域 块作用域 变量定义位置 函数作用域 函数原型作用域 ​​​​​​​ 特殊情况 文件作用域 链接 无链接 内部链接 外部链接 存储期 自动存储期 静态存… · 2026/11/6 6:16:10

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:27:59

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:03

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:07

三菱PLC数据采集到数据库的时序设计:Python+MC协议实战
三菱PLC数据采集到数据库的时序设计:Python+MC协议实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/6 1:02:11

ASIC主模式RTL设计:状态机与三态驱动的流片级实现
ASIC主模式RTL设计:状态机与三态驱动的流片级实现

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/6 1:02:11

STM32嵌入式C++开发:GDB调试与Renode仿真实战指南
STM32嵌入式C++开发:GDB调试与Renode仿真实战指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/6 1:02:11

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:27:59

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:03

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:07

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码