摩尔投票算法(双角度理解)

简介

摩尔投票算法(Boyer–Moore majority vote algorithm),是一个在O(n)的时间复杂度和O(1)的空间复杂度下寻找线性表中出现一半以上元素的算法,采用流的思想处理数据。

场景

如何在任意多的候选人(选票无序),选出获得票数具有压倒性优势的的那个?(此人得票超过其他所有人之和,即占1/2以上)。

当选票有序时,这个问题非常简单,因为整个线性表的中位数必定在长度超过1/2的段中:段在开头,则段尾一定超过1/2,段在结尾,则段头一定小于1/2。我们只需要检查线性表的中位数即可得到结果,时间复杂度为O(1)。

当选票无序时,想采用这种方法则必须对线性表进行排序,时间复杂度就会增长到所采用排序算法的时间复杂度。

那么有没有办法只顺序访问一遍线性表就能获得答案的方法呢?那就是摩尔投票法。

原理

摩尔算法的核心思想是任意元素两两抵消,最后剩下的元素一定是出现次数超过1/2的,算法维护一个序列元素num和一个计数器,num指示当前数字,计数器指示此元素还可以抵消几个元素。

我们访问下一个元素时,多种情况,这里介绍两种思维方式:count为中心元素为中心

Count为中心

  • count=0:前面的元素都两两抵消,应该将num指向当前元素,count=1
  • count>0:和当前元素相同:应该将count+1;和当前元素不同:应该将count-1

元素为中心

  • 和当前元素相同:应该将count+1
  • 和当前元素不同:如果count>1,抵消两个元素,应该将count-1;如果count=0,说明前面的元素都被抵消了,应该将num指向新元素,count=1

执行完毕后,余下的num即是出现次数最多的

例子

数组中出现次数超过一半的数字

LeetCode题目链接

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。你可以假设数组是非空的,并且给定的数组总是存在多数元素。

以count为中心的解法

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int num = 0;

        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                num = nums[i];
                count = 1;
            } else {
                if (nums[i] == num) {
                    count++;
                } else {
                    count--;
                }
            }
        }

        return num;
    }
}

以元素为中心的解法

class Solution {
    public int majorityElement(int[] nums) {
        int count = 1;
        int num = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // 元素相同
            if (nums[i] == num) {
                count++;
                continue;
            }

            // 元素不同
            if (count > 0) {
                count--;
            } else if (count == 0) {
                count++;
                num = nums[i];
            }
        }

        return num;
    }
}

Azure99

计算机专业学生,已经大三啦,是只休闲音游玩家,喜欢折腾vps、玩机,偶尔写写代码

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注