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

简介

摩尔投票算法(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;
    }
}