Leetcode刷题笔记:多数元素(摩尔投票算法最通俗的理解)

本文主要是介绍Leetcode刷题笔记:多数元素(摩尔投票算法最通俗的理解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述
关键点:

  • 给定的数组总是存在多数元素。
  • 出现次数大于 ⌊ n / 2 ⌋ \lfloor n/2\rfloor n/2

说明下面这种情况不会出现在测试用例中:

[3,3,3,2,2,2,4] 或 [3,3,3,2,2,2]

也就是刚好有2个频率等于 ⌊ n / 2 ⌋ \lfloor n/2\rfloor n/2 的元素

按照进阶要求,设计一个时间复杂度为 O(n)、空间复杂度为 O(1) 的算法,可以使用摩尔投票算法(Boyer-Moore Voting Algorithm)来解决这个问题。

摩尔投票算法

通俗地理解,这是一场战斗游戏,游戏设定战斗结束时必定有且只有1个存活者(candidate) ,最终返回的多数元素相当于存活者。战斗开始时(count==0) ,我们先把第一个元素设置为存活者,并且给第一个元素赋予初始生命值1滴血,之后的循环过程相当于是战斗过程,只要碰见一个与当前存活者相同的元素,无需战斗,就给他生命值+1滴血(count += 1),只要碰见一个和当前存活者不同的元素就需要战斗,战斗的结果就是消耗1滴血(count += -1),只要当前的 count 不为 0,当前这个存活者就还“活着”,不会被更换,直到最后,战斗结束时,必然会有一个最终的存活者,这个存活者就是多数元素。

这个“活着”的概念可以理解为 candidate 元素仍然有足够的力量继续和其他不同的元素对抗或抵消。

C++ 代码实现:

#include <vector>class Solution {
public:int majorityElement(std::vector<int>& nums) {//初始化计数器和候选者int count = 0;int candidate = 0;// 摩尔投票算法for (int num : nums) {//首先,设置或更换 candidate(在计数器为 0 时)。//如果是第一个元素则是设置,否则是被抵消完之后的更新if (count == 0) {candidate = num;}//然后,根据当前元素是否与当前候选者相同对计数器进行更新count += (num == candidate) ? 1 : -1;}//循环结束,返回多数元素return candidate;}
};

刚进入for循环时,变量 count 的值并非是当前 candidate 元素的总出现次数,而是当前循环步骤中当前 candidate 元素经过抵消后的出现次数。

当我们遇到一个与当前 candidate 不相同的元素时,count 减 1 是因为这些不同的元素可能代表着一个和 candidate 具有相同频率的另一类元素。因此,我们可以将当前的 candidate 和这个不同的元素看作是一对“相互抵消”的元素。

candidate 变量存储当前的候选元素。

具体过程可以这样理解:

  • 当我们遇到与 candidate 相同的元素时,count 增加,表示它的力量增强。
  • 当我们遇到与 candidate 不同的元素时,count 减少,表示它与这个不同元素互相抵消了一部分力量。
  • 只有当 count 减少到 0 时,表示当前的 candidate 被完全抵消掉了,它已经没有足够的力量继续作为候选元素,此时我们需要选择一个新的元素作为新的 candidate

所以,只要 count 不为 0,当前的 candidate 还在“战斗”,它还是有可能是多数元素,只有当它被完全抵消(count = 0)时,才会更换新的候选者。

这个“抵消战斗”的机制确保了多数元素(出现次数超过一半的那个元素)在整个数组遍历过程中会存活下来,并最终成为剩下的那个“胜者”。

count == 0 的可能情况

当前元素是数组的第一个元素时 count 为 0 外,还有另一种情况会导致计数为 0,即 候选元素和其他不同元素相互抵消 的过程中。

具体来说,当候选元素的计数减少到 0 时,说明之前的候选元素已经被后续元素抵消完了(遇到了和候选元素出现次数一样多的与候选元素不相同的元素)。在这种情况下,算法认为当前的候选元素不再是有效的多数元素,因此需要选择下一个未抵消的元素作为新的候选者。这发生的场景通常是:

  1. 候选元素的频率和非候选元素频率相同:如果数组中存在的元素并不是立即连续重复的,当前候选元素可能会逐渐被其他元素的不同值抵消,最终 count 变为 0。例如[3,2,3,4,3,6,3]count 的变化情况是[1,0,1,0,1,0,1],在经过元素 6 的循环步骤之后,count == 0 ,由于题目描述必定存在多数元素,所以最后一个元素必定是 3。经过最后一次循环步骤之后,count == 1

  2. 当前候选元素遇到了足够多的与它不同的元素:当某一个候选元素不断被与它不同的元素抵消时,count 逐渐减少到 0,此时下一个未抵消的元素会成为新的候选者。例如[3,3,3,1,4,7,3]count 的变化情况是[1,2,3,2,1,0,1],在经过元素 7 的循环步骤之后,count == 0 ,同样,由于题目描述必定存在多数元素,所以最后一个元素必定是 3。经过最后一次循环步骤之后,count == 1

这个算法的时间复杂度是 O(n),因为我们只需要遍历一次数组,空间复杂度是 O(1),因为我们只使用了常量级别的额外空间。

这篇关于Leetcode刷题笔记:多数元素(摩尔投票算法最通俗的理解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1140454

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

CSS3中使用flex和grid实现等高元素布局的示例代码

《CSS3中使用flex和grid实现等高元素布局的示例代码》:本文主要介绍了使用CSS3中的Flexbox和Grid布局实现等高元素布局的方法,通过简单的两列实现、每行放置3列以及全部代码的展示,展示了这两种布局方式的实现细节和效果,详细内容请阅读本文,希望能对你有所帮助... 过往的实现方法是使用浮动加

深入理解Apache Airflow 调度器(最新推荐)

《深入理解ApacheAirflow调度器(最新推荐)》ApacheAirflow调度器是数据管道管理系统的关键组件,负责编排dag中任务的执行,通过理解调度器的角色和工作方式,正确配置调度器,并... 目录什么是Airflow 调度器?Airflow 调度器工作机制配置Airflow调度器调优及优化建议最