你听说过摩尔投票法吗?

简介: 你听说过摩尔投票法吗?

前言


前几天在刷力扣题目时,看官方题解发现的算法,我感觉这个算法非常有意思,是一个很好的思维开拓,因此我整理摩尔投票算法的一些知识,分享给大家。


摩尔投票法


博耶-摩尔多数投票算法( Boyer–Moore majority vote algorithm ),中文常作多数投票算法、摩尔投票算法等,是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。


算法思想


在集合中寻找可能存在的多数元素,这一元素在输入的序列重复出现并占到了序列元素的一半以上;在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数,确定其是否为众数;如果一个序列中没有占到多数的元素,那么第一次的结果就可能是无效的随机元素。


过程可以分为两个阶段:


  • 投票阶段: 即投票人之间票数进行抵消
  • 计数阶段: 计算对抗结果中最后剩下的那个候选人票数是否有效。


举个栗子


上面的文字属实有几分枯燥无味,下面咱们来举一个有趣的栗子:


斯巴达勇士们经过了无数年的奋斗,成立了斯巴达共和国,走上了社会主义道路


今天是斯巴达第一届人民代表大会,会议将通过全民选举的方式选出第一届共和国主席。为了保证主席的权威性,只有得票数过半才能成为新共和国的领袖。


但现在斯巴达几百万人口,统计选票是个大问题啊。而且我斯巴达勇士勇猛无敌,岂能浪费在算数上。会议组织人绞尽脑汁,终于想出了一个绝妙的点子,不仅可以选出共和国领袖,也可以展现斯巴达共和国的勇武。


规则是这样的:


  1. 如果两个勇士选举意见不合,就去场外打一架,投票阶段就不要回来了。所有选举意见不合的都去激情对撞了,剩下的斯巴达勇士(可能有多个)意见肯定统一,他们的选举对象有可能就是最后的主席。
  2. 但如果光靠剩下的人判断领袖是存在漏洞的,例如 [1,2,2,1,3,3] 这种,前面两个候选人选票互相内耗了,第三个候选人也没有达到总票数的一般,因此还需要计数阶段,统计一下最后所剩候选人的票数是否达到总票数的一半。


图文讲解


看完阿包举的例子如果还不懂,咱们再来看个图文的。


思路


根据上面的算法思想,我们将当前票数最多的候选人与获得的票数(抵消后)分别存储在 majorcount 中。


当我们遍历下一个选票时,判断当前 count 是否为零:


  • 如果 count == 0 : 代表 major 空缺,直接将当前候选人赋值给 major,并将 count ++
  • count != 0 : 代表当前 major 的票数未被完全抵消,令 count --,不同意见的斯巴达勇士去激情对撞。


初始值 count = 0, major = -1

详细图解[2,2,1,3,1,2,2] 为例。


遍历数组第一个元素 2,因 count == 0,所以将 2 赋值给 major,且票数 count  = 1


image.png


第二个数组元素依旧是候选人 2,得票数 count ++


image.png


第三个元素是 1,与 major 冲突,因此发生激情对撞,当前 major 的票数抵消 1 票。


image.png


第四个元素是 3, 与 major 冲突,产生激情对撞,当前 major 的票数抵消一票。


image.png


当遍历到第五个元素 1 时,此时 count = 0,说明 marjor 位置空缺,所以令 majro = 1,且 count = 1


image.png


第六个元素是 2,与 major 冲突,产生激情对撞,当前 major 的票数抵消 1 票,此时 count 又变为 0


image.png


遍历最后一个元素 2,当前 count = 0,说明 marjor 位置空缺,所以令 majro = 1,且 count = 1


image.png


遍历完毕,2 元素很有可能就是斯巴达新的领袖。


计数阶段: 统计 2 元素出现的次数是否大于一半,2 出现四次,大于一半,所以我宣布斯巴达共和国未来的领袖就是 2 了(怎么听起来怪怪的。。。)


真题实战


真题一:主要元素


题目来源: 面试题 17.10. 主要元素


题目描述:数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组,找出其中的主要元素。若没有,返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案


如果没有最后一句要求,肯定咱们大脑中第一瞬间想到的就是哈希表,使用哈希表存储每个元素的出现次数。


但是咱们现在可不是凡人啊,连斯巴达共和国的领袖都可以选举出来了,肯定要上摩尔选举法啊。


这个题的思想与我举得图文讲解极度类似,我就不多做赘述了。


/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let major = -1;
    let count = 0;
    for (var i = 0; i<nums.length; i++) {
        if (count === 0) {
            major = nums[i];
        }
        if (nums[i] === major) {
            count++;
        } else {
            // 票数抵消
            count--;
        }
    }
    count = 0;
    const length = nums.length;
    // 计数阶段
    for (var i = 0; i<nums.length; i++) {
        if (nums[i] === major) {
            count++;
        }
    }
    return count * 2 > length ? major : -1;
};
复制代码


真题二:求众数 II


题目来源: 229. 求众数 II


题目描述:给定一个大小为 n 的整数数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案


我当时刷这道题时苦思冥想,咋都想不出空间复杂度为 O(1)的解决方案,看官方题解醍醐灌顶,这也能摩尔投票法。咱们来一起分析一下:


做这个题之前,首先要理解:出现超过 ⌊ n/3 ⌋ 次的元素最多有 2 个。咱们可以稍微反证一下:如果出现了 2 个以上超过 ⌊ n/3 ⌋ 次的元素,例如 3 个,哪意味着当前数组中会存在 3 * ⌊ n/3 ⌋ > n,与现实冲突。


思路


我把这个题形象一下,其实就相当于斯巴达勇士们要选正副领袖,所以现在两个不同意见得勇士打架就不合理了,因为这两个勇士的候选人可能是正副领袖。


既然是要选两个领袖,那是不是也可以类比为三个不同意见得勇士打架抵消那,下面我们来具体操作一下,看看能不能实现:


如果数组中只有一个元素 x 超过了 ⌊ n/3 ⌋,把数组分为两部分:一部分为 kx,另一部分为 (n-k)/3 组三个不同的元素,如果三个不同元素会被抵消,最终只会剩下 kx


如果数组中有两个元素 x,y 超过了 ⌊ n/3 ⌋,把数组分为三部分:第一部分为 kx,第二部分为 ly,第三部分为 (n-k-l) / 3 组三个不同的元素,如果三个不同元素会被抵消,最终会剩下 kxly


通过上面得分析,三个不同意见的勇士相抵消是可以实现的,算法流程为:


  • 检查当前元素是否为第一个选中的元素或第二个选中的元素。如果存在相同,对应元素得票数加一。
  • 如果与两个元素都不相同,则三个不同得元素抵消一次
  • 抵消结束后,若存在最终选票大于 0 得元素,进行计数阶段,检查该元素次数是否大于 ⌊ n/3 ⌋


上代码:


/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function(nums) {
    let major1 = 0,
        major2 = 0,
        count1 = 0,
        count2 = 0;
    const length = nums.length;
    // 投票抵消阶段
    for (let i = 0; i<length; i++) {
        if (count1 > 0 && major1 === nums[i]) {
            count1 ++;
        }else if (count2 > 0 && major2 === nums[i]) {
            count2 ++;
        }else if (count1 === 0) {
            count1 ++;
            major1 = nums[i];
        }else if (count2 === 0) {
            count2 ++;
            major2 = nums[i];
        }else {
            count1 --;
            count2 --;
        }
    }
    // 计数阶段
    let cnt1 = 0, cnt2 = 0, res = [];
    for (let i = 0; i<length; i++) {
        if (count1 > 0 && major1 === nums[i]) {
            cnt1 ++;
        }
        if (count2 > 0 && major2 === nums[i]) {
            cnt2 ++;
        }
    }
    if (count1 > 0 && cnt1 > Math.floor(length / 3)) {
        res.push(major1);
    }
    if (count2 > 0 && cnt2 > Math.floor(length / 3)) {
        res.push(major2);
    }
    return res;
};
复制代码

往期精彩文章





相关文章
|
6月前
|
存储 算法
摩尔投票的原理详解
摩尔投票的原理详解
148 1
|
6月前
|
数据采集 人工智能 算法
大模型时代:一群人的狂欢,一个人的孤单!
大模型时代:一群人的狂欢,一个人的孤单!
61 5
|
算法 JavaScript Android开发
LeetCode 周赛上分之旅 #33 摩尔投票派上用场
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
77 0
|
程序员 决策智能
博弈论(一)——产品小哥哥的民主妙计
博弈论(一)——产品小哥哥的民主妙计
89 0
|
存储 人工智能 自然语言处理
ChatGPT 大智近妖,从宇宙人生到手搓光刻机,从哄女朋友到写年终总结我们聊得非常开心,反而让人越来越忧心
都说 ChatGPT 要干掉程序员,清理搜索引擎,取代 Stack Overflow,还能消灭人类,这些有些言过其实了。ChatGPT 的定位是一个人工智能助理,它说,它的主要目的是通过回答用户的问题,为用户提供帮助。在体验了一天后,我相信对它的调教是成为一个正直的人,它也是这样做的。 它谦虚有礼,无疑是一个合格的助理,确实可以为我们提供很大的帮助。生成的回答条理清晰,思路明确,令人信服。但是从刚接触的惊奇开心过后,随着时间推移,我却越来越忧心了。 以下的内容是我的体验过程和其中的思考,其中引用的部分为 ChatGPT 的回答内容。希望对你了解它有一些帮助。
347 1
ChatGPT 大智近妖,从宇宙人生到手搓光刻机,从哄女朋友到写年终总结我们聊得非常开心,反而让人越来越忧心
|
人工智能 算法 Java
摩尔投票法
摩尔投票法
181 0
|
算法 网络架构 计算机视觉
“玩命”活着——致敬每一位互联网创业者
九月末的杭州,满城桂花飘香。西湖区文一西路176号的一处民宅里灯火通明,深夜的微凉,丝毫没有影响里面激烈讨论的人们。产品经理樱木和商务拓展由芝在一个问题上争执不,内容是关于产品量产的时间问题。
229 0
“玩命”活着——致敬每一位互联网创业者
|
数据采集 人工智能 算法
经历分享|这些图灵奖主原来就藏在身边
这是一个真实的故事,在笔者今年参加考研复试的时候,发现了一些有趣的联系!
725 0
|
人工智能
【话题】致敬伟大的科学家史蒂芬·霍金,他留下的预言能实现吗?
版权声明:本文为 testcs_dn(微wx笑) 原创文章,非商用自由转载-保持署名-注明出处,谢谢。 https://blog.csdn.net/testcs_dn/article/details/79556218 据英国天空新闻等多家媒体3月14日消息,史蒂芬·霍金去世,享年76岁。
942 0