美文网首页
高效寻找数组中的“众数” - 摩尔投票法

高效寻找数组中的“众数” - 摩尔投票法

作者: M_lear | 来源:发表于2019-02-06 16:07 被阅读0次

问题:在长度为n的数组中找出重复次数超过n/2的数(假设一定存在)。

存在O(n)的时间复杂度和O(1)的空间复杂度的解法,即摩尔投票法

前言: 直接看摩尔投票法的代码,很难理解其算法思想,过一段时间就会忘记代码怎么写的,在此之前其实我就已经看过不下两次代码了,只记得有这样一种方法,但是具体的就不记得了,所以我们要理解其原理。

摩尔投票法

摩尔投票法基于这样一个事实,当一个数的重复次数超过数组长度的一半,每次将两个不相同的数删除,最终剩下的就是要找的数。

那么如何在O(n)的时间复杂度,只遍历一次数组就把不同的数都删除呢?摩尔投票法的代码实现是具有技巧性的,并不是真的要删除数组里的数,只是把遍历过程当作一个删除过程。

使用一个虚拟数组存放还未和不同数字一起删除的数,这个数组只能有若干个同一数字,不可能存在不同的数,因为如果存在不同的数就会被删去,而不会放到此数组中。

当数组遍历到当前元素时,若虚拟数组为空,就将当前元素加进去;若虚拟数组非空,就比较当前元素是否和虚拟数组中的元素相同,如果不同就删去虚拟数组中的一个元素,同时当作当前元素也被删除,接着遍历下一元素,这样就相当于一对不同的数字被删除,如果相同,就把当前元素加到虚拟数组中。最终遍历完数组,虚拟数组中的元素就是要找的元素。

由于虚拟数组中只会存在若干个相同元素,那么可以仅用两个变量表示这个虚拟数组,一个变量存值,另一个变量存放个数。

更详细的描述可以参考知乎上喝七喜的回答

c语言代码如下:

#include<stdio.h>
#define LEN 10
int main(){
    int a[] = {2,2,1,1,1,3,3,1,1,1};
    int x, cx = 0;//表示一个虚拟数组
    for(int i = 0; i < LEN; ++i){
        if(cx == 0) x = a[i], cx = 1;//虚拟数组为空,加入当前元素
        else if(x == a[i]) ++cx;//数组非空,当前元素与虚拟数组元素相同,加入当前元素
        else --cx;//数组非空,当前元素与虚拟数组元素不同,删除一对不相同的元素
    }
    printf("超过1/2的数是:%d",x);
    return 0;
}

类似的问题: 在长度为n的数组中找出重复次数超过n/3的数(不一定存在)。

容易知道,重复次数超过数组长度1/3的数最多有两个。用反证法容易证得。

同样的思路,使用两个虚拟数组,每次删除三个不同的数,最终虚拟数组中的两个数就是可能的答案,此时再遍历一遍数组,做一个验证即可。
c语言代码如下:

#include<stdio.h>
#define LEN 8
int main(){
    int a[] = {1,2,1,2,3,3,1,2};
    int x, y, cx = 0, cy = 0;//两个虚拟数组
    for(int i = 0; i < LEN; ++i){
        if(x == a[i]) ++cx;
        else if(y == a[i]) ++cy;
        else if(cx == 0) x = a[i], cx = 1;
        else if(cy == 0) y = a[i], cy = 1;//这两个判断不能提前,因为可能把x,y赋为同一个值
        else --cx, --cy;
    }
    cx = 0,cy = 0;
    for(int i = 0; i < LEN; ++i){//锁定候选目标,遍历数组,计数,做验证
        if(a[i] == x) ++cx;
        else if(a[i] == y) ++cy;
    }
    if(cx > LEN/3){
        printf("超过1/3的数有:%d\n",x);
    }
    if(cy > LEN/3){
        printf("超过1/3的数有:%d\n",y);
    }
    return 0;
}

相关文章

  • 高效寻找数组中的“众数” - 摩尔投票法

    问题:在长度为n的数组中找出重复次数超过n/2的数(假设一定存在)。 存在O(n)的时间复杂度和O(1)的空间复杂...

  • LeetCode—— 多数元素

    题目描述 一、CPP 1. 摩尔投票法: 解题思路:如果我们把众数记为 +1,把其他数记为 −1 ,将它们全部加起...

  • 力扣题解(数组)

    26. 删除排序数组中的重复项 面试题 16.21. 交换和 面试题 17.10. 主要元素 摩尔投票法 15. ...

  • 使用摩尔投票法解决多数问题

    1、什么是摩尔投票法 博耶-摩尔多数投票算法(英语:Boyer–Moore majority vote algor...

  • 摩尔投票法

    提问: 给定一个int型数组,找出该数组中出现次数大于数组长度一半的int值。 解决方案: 遍历该数组,统计每个i...

  • 摩尔投票法

    摩尔投票法又叫多数投票法。 解决的问题如何在任意多的候选人中,选出获得票数最多的那个 算法包括两个阶段 1. 对抗...

  • 摩尔投票法

    题目描述 给定一个大小为 n 的数组,找出其中所有出现超过 ⌊ n/2 ⌋ 次的元素。 分析:采用摩尔投票法,两个...

  • LC数组题目分类详解

    leetcode 169 求众数下面代码给出: 哈希法/排序法/投票法 哈希法:用map统计个数,直接计算即可排序...

  • 169. 多数元素

    169. 多数元素 经典面试题 摩尔投票法

  • 摩尔投票法——1比1火拼 2020-03-17(未经允许,禁止转

    摩尔投票法的基本问题 给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2...

网友评论

      本文标题:高效寻找数组中的“众数” - 摩尔投票法

      本文链接:https://www.haomeiwen.com/subject/eucisqtx.html