`
mabusyao
  • 浏览: 252599 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

摩尔投票法

 
阅读更多

摩尔投票法

 

提问: 给定一个int型数组,找出该数组中出现次数最多的int值。

 

解决方案: 遍历该数组,统计每个int值出现次数,再遍历该集合,取出出现次数最大的int值。

 

这算是一个比较经典的解决办法,其中可能会用到Map来做统计。如果不使用Map,则时间复杂度会超过线性复杂度。除此之外,也没有什么特别好的办法。

 

今天在leetcode上遇到这样一道题目,

 

提问: 给定一个int型数组,找出该数组中出现次数大于数组长度一半的int值。

 

解决方案: 遍历该数组,统计每个int值出现次数,再遍历该集合,找出出现次数大于数组长度一半的int值。

 

同样的,该解决办法也要求使用Map,否则无法达到线性的时间复杂度。

 

那么对于这个问题,有没有什么不使用Map的线性算法呢?

 

答案就是今天我们要提到的摩尔投票法。利用该算法来解决这个问题,我们可以达到线性的时间复杂度以及常量级的空间复杂度。

 

首先我们注意到这样一个现象: 在任何数组中,出现次数大于该数组长度一半的值只能有一个

 

通过数学知识,我们可以证明它的正确性,但是这并不在我们这篇博客里涉及。

 

摩尔投票法的基本思想很简单,在每一轮投票过程中,从数组中找出一对不同的元素,将其从数组中删除。这样不断的删除直到无法再进行投票,如果数组为空,则没有任何元素出现的次数超过该数组长度的一半。如果只存在一种元素,那么这个元素则可能为目标元素。

 

那么有没有可能出现最后有两种或两种以上元素呢?根据定义,这是不可能的,因为如果出现这种情况,则代表我们可以继续一轮投票。因此,最终只能是剩下零个或一个元素。

 

在算法执行过程中,我们使用常量空间实时记录一个候选元素c以及其出现次数f(c),c即为当前阶段出现次数超过半数的元素。根据这样的定义,我们也可以将摩尔投票法看作是一种动态规划算法

 

程序开始之前,元素c为空,f(c)=0。遍历数组A:

 

* 如果f(c)为0,表示截至到当前子数组,并没有候选元素。也就是说之前的遍历过程中并没有找到超过半数的元素。那么,如果超过半数的元素c存在,那么c在剩下的子数组中,出现次数也一定超过半数。因此我们可以将原始问题转化为它的子问题。此时c赋值为当前元素, 同时f(c)=1。

* 如果当前元素A[i] == c, 那么f(c) += 1。(没有找到不同元素,只需要把相同元素累计起来)

* 如果当前元素A[i] != c,那么f(c) -= 1 (相当于删除1个c),不对A[i]做任何处理(相当于删除A[i])

 

如果遍历结束之后,f(c)不为0,则找到可能元素。

 

再次遍历一遍数组,记录c真正出现的次数,从而验证c是否真的出现了超过半数。上述算法的时间复杂度为O(n),而由于并不需要真的删除数组元素,我们也并不需要额外的空间来保存原始数组,空间复杂度为O(1)。

 

看java代码示例,为了保证每一步骤的清晰性,代码没有经过优化。

    /**
     * 算法基础:摩尔投票法
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {

        int majority = -1;

        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                majority = num;
                count++;
            } else {
                if (majority == num) {
                    count++;
                } else {
                    count--;
                }
            }
        }

        int counter = 0;
        if (count <= 0) {
            return -1;
        } else {
            for (int num : nums) {
                if (num == majority) counter ++;
            }
        }

        if (counter > nums.length / 2) {
            return majority;
        }

        return -1;
    }

 

其实这样的算法也可以衍生到其它频率的问题上,比如说,找出所有出现次数大于n/3的元素。同样可以以线性时间复杂度以及常量空间复杂度来实现。

 

 

 

分享到:
评论

相关推荐

    摩尔投票法_inventedyv3_摩尔投票法_DEMO_投票法_

    摩尔投票法,又称多数裁决法,是一种在有限个选项中寻找大多数元素的算法,由摩尔(W. W. Moore)提出。这个方法在分布式系统、容错计算和选举系统等领域有一定的应用,尽管其实际应用场景并不广泛,但其简洁而巧妙...

    大厂面试系列二.pdf

    找出数组中出现次数超过一半的数,可以使用摩尔投票法。该算法基于一个事实,即如果某个数是数组中出现次数最多的数,那么它出现的次数会超过其他所有数出现次数之和。 找出被修改过的数字问题,如果无法使用额外的...

    3众数问题详解.zip

    摩尔投票法是一种在线算法,可以在一次遍历数据流的过程中找到众数。基本思想是每次遇到一个数,就将它与其他数进行比较,消除非众数。具体操作是将每个数看作一票,每次比较时,如果发现两个不同的数,就相互抵消...

    腾讯2016研发工程师编程题及答案.pdf

    解决这个问题,可以使用摩尔投票法(Moore Voting Algorithm),它是一种简单且线性时间复杂度的算法。基本思想是每次比较两个不同的元素并消除它们,重复此过程直到只剩下一个元素,这个元素就是多数元素。如果在...

    php-leetcode题解之求众数.zip

    在PHP中解决这个问题,我们可以采用多种方法,例如“Boyer-Moore Voting Algorithm”(鲍耶-摩尔投票法)或者简单的计数法。这里我们将重点讨论这两种方法。 1. **Boyer-Moore Voting Algorithm**: 这个算法的...

    前端大厂最新面试题-segment-tree.docx

    3. **子数组中占绝大多数的元素**:这个问题需要找出数组中出现次数超过数组长度一半的元素,可以结合线段树和摩尔投票法。线段树可以快速统计每个区间内的元素计数,而摩尔投票法则可以有效去除重复元素,找出候选...

    zhongshu.rar_zhongshu

    3. **摩尔投票法(Moore's Voting Algorithm)**:这是一种在线性时间复杂度内找到众数的算法。其核心思想是每次比较两个不同的元素,若不同则消去两者,直到只剩下一个元素,这个元素即为众数。该方法适合大数据集...

    算法实验第一次实验报告1

    众数问题是指找出数据集中出现次数最多的元素,可以使用摩尔投票法这样的分治策略来解决。整数因子分解问题,尤其是大整数的因子分解,是一个经典难题,可以使用递归尝试所有可能的因子来寻找分解。 总的来说,这个...

    php数组的一些常见操作汇总

    解决这个问题可以采用摩尔投票法(Boyer-Moore Majority Vote Algorithm)。基本思想是设置一个当前值和当前值的计数器,初始化当前值为数组首元素,计数器值为1。然后从第二个元素开始遍历整个数组,如果计数器值...

    算法-理论基础- 排序- 逆序对问题(包含源程序).rar

    例如,一种叫做“摩尔投票法”的线性时间复杂度方法可以用来求解两个序列的逆序对总数,但这种方法不适用于单个序列的逆序对计算。 在实际应用中,逆序对问题可能出现在数据分析、数据库索引优化、机器学习模型的...

    前端大厂最新面试题-array.docx

    求众数 II`):这类问题需要找出数组中出现次数最多的元素,可以使用摩尔投票法(Moore Voting Algorithm)快速找出多数元素。 10. **数组中重复的数据**(如`442. 数组中重复的数据`):这类问题要求找出数组中...

    算法经典面试题

    这是摩尔投票法的应用,用于找出数组中出现次数超过一半的元素。通过不断地将成对的不同元素剔除,最后剩下的元素即为目标元素。 7. **排序大量小整数**: 题目中给出了内存限制和数字范围。可以使用位操作来解决...

    关于数组的几道面试题1

    这通常使用摩尔投票法来解决,通过一轮轮地消除其他元素,最终剩下的是出现次数超过一半的元素。 5. **求数组中元素的最短距离**: 需要遍历数组,记录元素出现的位置,找到相邻出现的元素之间的最小距离。 6. *...

    滴滴Java工程师岗位面试真题

    可以使用布隆过滤器快速剔除不可能的元素,然后使用摩尔投票法找出出现次数最多的三个数字。 7.1.8 找出1到n+2中缺失的两个数: 利用异或操作,1到n+2的异或结果为0,所以任意两个缺失数字的异或结果即为缺失的两个...

    算法题总结 2741

    13. **数组中出现次数超过一半的数字**:摩尔投票法(Majority Voting Algorithm)是解决这类问题的经典方法。 14. **数组中最小的 k 个数**:可以使用快速选择算法或者优先队列(堆)来寻找最小的k个数。 15. **...

    众数问题 算法分析与设计

    4. **摩尔投票法(Moore Voting Algorithm)**:这是一种常用于找出单个众数的有效方法。每次比较两个不同的元素,将它们“抵消”掉,直到只剩下一个元素,这个元素就是众数。这种方法在最坏情况下也需要O(n)时间,...

    ZhongShu.rar_递归众数

    在实际应用中,更常见的做法是使用摩尔投票法或哈希表等非递归方法来查找众数,它们的时间复杂度更低,适用于大数据集。 总结来说,"ZhongShu.rar_递归众数" 提供了一个使用递归方法寻找整数数组众数的例子。虽然...

    剑指offer前10题python代码

    1. **数组中出现次数超过一半的数字**:这道题目要求找出数组中出现次数超过一半的元素,常见解法是摩尔投票法。Python实现中,可以使用两个变量交替记录最大值和出现次数,最终得到的即为目标元素。 2. **两个数组...

    剑指offer编程题66道题目描述及java代码实现汇总

    1. **数组中出现次数超过一半的数字**:这是一道常见的计数问题,可以使用摩尔投票法(Majority Vote Algorithm)解决,避免使用排序或哈希表。 2. **二维数组中的查找**:在给定的二维矩阵中寻找特定元素,可以...

Global site tag (gtag.js) - Google Analytics