首页 > 编程语言 >[leetcode刷题]面试经典150题之5多数元素元素(简单)【附Boyer-Moore 投票算法(摩尔投票法)】

[leetcode刷题]面试经典150题之5多数元素元素(简单)【附Boyer-Moore 投票算法(摩尔投票法)】

时间:2024-09-20 22:49:25浏览次数:12  
标签:count 150 candidate nums 元素 投票 数组 多数

很有意思的一个题,想了半天没想出来,最后发现两行代码就做出来了。写完后学习到还可以用Boyer-Moore 投票算法,能减小空间复杂度,我把它写在后面,可以进一步学习。

题目  多数元素

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

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

解决思路

这个题的重点是多数元素大于总元素的n/2,也就是说这个数组中超过一半的数都是这个数。那么我们可以将元素排序,无论n为奇还是偶,int(n/2)的位置一定是这个多数元素。

代码

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[int(len(nums)/2)]

Boyer-Moore 投票算法详解

Boyer-Moore 投票算法是一种用于寻找多数元素的经典算法。它可以在 O(n) 的时间复杂度和 O(1) 的空间复杂度下找到数组中的多数元素。

多数元素定义:

多数元素是指在一个长度为 n 的数组中,出现次数超过 n/2 的元素。例如,在数组 [3, 3, 4, 2, 3, 3, 3] 中,元素 3 是多数元素,因为它出现了 5 次,超过了数组长度的一半(7 / 2 = 3.5)。

算法思路:

Boyer-Moore 投票算法基于一个简单但有效的贪心思想:通过配对和抵消的方式找到多数元素。具体过程如下:

  1. 假设:我们假设数组中确实存在一个多数元素,它的出现次数大于 n/2
  2. 配对与抵消
    • 初始化一个候选元素,并设置它的计数器为 1。
    • 遍历数组,当遇到与当前候选元素相同的元素时,增加计数器;当遇到不同的元素时,减少计数器。
    • 如果计数器为 0,意味着当前候选元素的力量被完全抵消掉了,我们选择当前的元素作为新的候选元素,并将计数器重置为 1。
  3. 最终结果:遍历结束后,剩下的候选元素就是多数元素。
代码
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = None  # 初始化候选元素
        count = 0  # 计数器

        # 第一遍遍历找出候选元素
        for num in nums:
            if count == 0:  # 如果计数为0,更新候选元素
                candidate = num
            count += (1 if num == candidate else -1)  # 相同则+1,不同则-1

        # 返回最终的候选元素
        return candidate

学习这个算法的时候我有想会不会有有特殊情况使多数元素最后结果也是0,例如多数元素没隔一个出现一次的情况会什么样?会不会就不行了。答案是并不会,例如数组 [1, 3, 1, 3, 1, 3, 1],也可以通过 Boyer-Moore 投票算法找到多数元素。我们来看看这个过程如何进行。

nums = [1, 3, 1, 3, 1, 3, 1]
  1. 初始化 candidate = Nonecount = 0
  2. 遍历 nums
    • 第一个元素 1count == 0,所以 candidate = 1count = 1
    • 第二个元素 3,不同于 candidate,所以 count = 0
    • 第三个元素 1count == 0candidate = 1count = 1
    • 第四个元素 3,不同于 candidatecount = 0
    • 第五个元素 1count == 0candidate = 1count = 1
    • 第六个元素 3,不同于 candidatecount = 0
    • 第七个元素 1count == 0candidate = 1count = 1

最终 candidate1,正确找到了多数元素。

结论

  • 无论多数元素如何分布(连续或分散),只要它出现的次数超过 n/2,它就能在最后通过不断抵消其他元素最终胜出。
  • Boyer-Moore 投票算法依赖于这个“多数”特性,只要有超过半数的元素在数组中,它们的力量在与其他元素进行抵消时最终会保留下来。

标签:count,150,candidate,nums,元素,投票,数组,多数
From: https://blog.csdn.net/m0_63680328/article/details/142406695

相关文章

  • 每日一题:Leetcode-347 前K个高频元素
    力扣题目解题思路java代码力扣题目:给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。示例1:输入:nums=[1,1,1,2,2,3],k=2输出:[1,2]示例2:输入:nums=[1],k=1输出:[1]提示:1<=nu......
  • JMeter测试计划元素
    JMeter包含各种相互关联但为不同目的而设计的元素。在开始使用JMeter之前,最好先了解一下JMeter的一些主要元素,并详细说明。注意:测试计划包含至少一个线程组。以下是JMeter的一些主要组件:测试计划(TestPlan)线程组(ThreadGroup)控制器(Controllers)监听器(Listeners)计......
  • C++ std::find函数 容器元素查找
    简介std::find函数是C++标准库内非常实用的一个函数,主要用于在给定范围内查找某个元素,如果找到该元素,则返回指向该元素的迭代器;如果没有找到,则返回指向范围末尾的迭代器(即 end() )。find函数原型std::find在头文件algorithm中template<classInputIt,classT>Inp......
  • SC2569高性能电流模式PWM开关150W控制驱动
    SC2569结合了高度集成的电流模式PWM控制IC优化为高性能好,待机功耗低,成本低有效的脱机反激变换器应用。PWM正常工作时的开关频率为外部可编程和修剪到紧的范围内。在空载或轻载情况下,IC操作扩展的“突发模式”以最小化开关损耗。待机功率低,待机功率高这样就实现了转......
  • 开发者工具(F12)进行元素定位
    步骤1:打开开发者工具使用F12:打开你想要查找元素的网页。按F12键(或者右键点击页面,选择“检查”)以打开浏览器的开发者工具。选择Elements面板:在开发者工具中,通常会默认打开Elements面板。该面板显示网页的HTML结构和相关的CSS样式。步骤2:查找元素......
  • 算法-两数相加(150)
     我们首先创建一个虚拟头节点dummy,它的主要作用是简化边界条件的处理。然后,我们使用一个循环来遍历两个链表,同时考虑进位。在循环中,我们计算当前位的和(包括从上一个计算中可能遗留下来的进位),然后更新进位和当前节点。如果两个链表中的某个链表已经遍历完,我们将对应的值视为0......
  • 34. 在排序数组中查找元素的第一个和最后一个位置
    思路先判断target是否存在列表中,不存在直接输出存在,则找出第一个等于target值的列表位置,即目标值在列表中的开始位置接着在当前位置继续往下查找,找到最后一个目标值等于列表值的位置(也可用二分查找找到等于target值的位置+往前、往后找到开始、结束位置,但会超限,可参考(......
  • 火语言RPA流程组件介绍--设置元素属性值
    ......
  • Java关键字详解:构建Java语言的基础元素
    Java是一门静态类型、面向对象的编程语言,其基础构建块由一系列关键字(keywords)构成。这些关键字具有特定的功能和含义,定义了Java语言的结构和语法规则。Java关键字在编译时具有特殊意义,开发者不能将其用作变量、类或方法名。本文将详细解析Java中的关键字及其用途,并结合代码......
  • OpenAI以1500亿美元公司估值向投资者筹集65亿美元!安卓版谷歌Gemini Live免费上线|AI日
    文章推荐突发!OpenAI「Her」领头人离职!字节硬件与豆包联动,预推出AI耳机、眼镜等产品|AI日报今日热点安卓版谷歌GeminiLive免费上线据科技媒体9to5Google报道,谷歌在1个月前面向Advanced订阅用户推出后,正逐步面向所有安卓用户免费开放GeminiLive。GeminiLive采用了增强型语音引擎,可......