摩尔投票算法

摩尔投票算法也叫多数投票算法

摩尔投票法，解决的问题是如何在任意多的候选人中，选出票数超过一半的那个人。注意，是超出一半票数的那个人。

假设投票是这样的，[A, C, A, A, B]，ABC 是指三个候选人。
第一张票与第二张票进行对坑，如果票不同则互相抵消掉；
接着第三票与第四票进行对坑，如果票相同，则增加这个候选人的可抵消票数；
这个候选人拿着可抵消票数与第五张票对坑，如果票不同，则互相抵消掉，即候选人的可抵消票数 -1。

动画演示

应用

来源：leetcode 剑指offer 39

题目：求数组中出现次数超过一半的数字
要求：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

代码

//摩尔投票
int majorityElement(int* nums, int numsSize)
{
    int count = 0;
    int res = 0;
    for (int i = 0; i < numsSize; ++i)
    {
        if (count == 0)
        {
            ++count;
            res = nums[i];
        }
        else if (nums[i] == res)
        {
            ++count;
        }
        else
        {
            --count;
        }
    }

    return res;
}

测试截图

摩尔投票算法进阶版

来源：leetcode.229

题目：给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：[3,2,3]
输出：[3]
示例 2：
输入：[1,1,1,3,3,2,2,2]
输出：[1,2]

超过n/3的数最多只能有两个。先选出两个候选人A,B。 遍历数组，分三种情况：

1、如果投A（当前元素等于A），则A的票数++;
2、如果投B（当前元素等于B），B的票数++；
3、如果A,B都不投（即当前与A，B都不相等）,那么检查此时A或B的票数是否减为0：
3.1、 如果为0,则当前元素成为新的候选人；
3.2 、如果A,B两个人的票数都不为0，那么A,B两个候选人的票数均减一；

遍历结束后选出了两个候选人，但是这两个候选人是否满足>n/3，还需要再遍历一遍数组，找出两个候选人的具体票数。

动画演示

代码

int* majorityElement(int* nums, int numsSize, int* returnSize)
{
    int count1 = 0;
    int count2 = 0;
    int res1 = 0; //候选人1
    int res2 = 0; //候选人2
    int* arr = (int*)malloc(sizeof(int) * 2);
    for (int i = 0; i < numsSize; ++i)
    {
        if (res1 == nums[i])
        {
            ++count1;
            continue;
        }

        if (res2 == nums[i])
        {
            ++count2;
            continue;
        }
		
		// 第1个候选人配对
        if (count1 == 0)
        {
            res1 = nums[i];
            ++count1;
            continue;
        }
        
		// 第2个候选人配对
        if (count2 == 0)
        {
            res2 = nums[i];
            ++count2;
            continue;
        }

        --count1;
        --count2;
    }

	// 找到了两个候选人之后，需要确定票数是否满足大于 N/3
    count1 = count2 = 0;
    for (int i = 0; i < numsSize; ++i)
    {
        if (nums[i] == res1)
            ++count1;
        else if (nums[i] == res2)
            ++count2;
    }

    if (count1 > (numsSize / 3) && count2 > (numsSize / 3))
    {
        arr[0] = res1;
        arr[1] = res2;
        *returnSize = 2;
        return arr;
    }
    else if (count1 > (numsSize / 3))
    {
        arr[0] = res1;
        *returnSize = 1;
        return arr;
    }
    else if (count2 > (numsSize / 3))
    {
        arr[0] = res2;
        *returnSize = 1;
        return arr;
    }
    
    *returnSize = 0;
    return arr;

}

测试截图

总结

如果至多选一个代表，那他的票数至少要超过一半（⌊ 1/2 ⌋）的票数；
如果至多选两个代表，那他们的票数至少要超过 ⌊ 1/3 ⌋ 的票数；
如果至多选m个代表，那他们的票数至少要超过 ⌊ 1/(m+1) ⌋ 的票数。

问题：

有一个数组，里面是一些重复的数字。问是否存在一个数，这个数出现的次数超过了数组大小的一半？如果存在的话，这个数是多少？

例如对于数组[1,1,3,1,3,1,2]，数字1的出现的次数超过了数组的一半；
而对于数组[6,6,6,7,7,7]，没有数字超过数组的一半（数字6和7都出现了3次，出现的次数等于数组的一半，而没有超过数组的一半）

如果题目要求的是数字出现的次数大于等于数组的一半，那多数投票算法就失效了，只能用其他方法来实现。

解决方式：

对于这个问题，最佳的算法是多数投票算法，也叫作Boyer-Moore algorithm。
对这个问题，最大投票算法的时间复杂度是O(n)（总共遍历两次数组），空间复杂度是O(1)（总共维护两个变量）

算法的思想是，如果一个数存在超过数组的一半，则这个数和其他数相互抵消，最终还是会有自己的同党剩下来。
例如有一些人来投票，投的票选项分别是[1,3,2,1,1].
第一个人投1号，第二个人投3号，两个选票不同，相互抵消；
第三个人投2号，第四个人投1号，两个选票不同，相互抵消；
最后剩下一个1号投票，1号也是超过半数的投票号。

再看一个例子：[1,1,3,4,2]
第1、2个人的投票将选项1的票数累加到2；
第3、4个人的投票不是1，所以抵消选项1的票数到0；
最后一个人的投票是2.
但是很明显，2号不是多数的票号。所以我们需要再遍历一次数组来判断2号票是不是多数票。这个就是多数投票算法的思想。

JAVA实现：

public int majorityVote(int nums[]) {
	int candidate=0,count=0;
	for(Integer num : nums) {
		if(num==candidate) {
			count++;
		}else if(count==0) {
			candidate=num;
			count=1;
		}else {
			count--;
		}
	}
	
	count=0;
	for(Integer num : nums)
		if(num==candidate)	count++;
	if(count>Math.ceil(nums.length/2))	return candidate; 
	return -1;    // 表示没有超过半数的票
}

传进函数的参数nums数组表示选票的票号，candidate表示可能的多数票号，初始值就设为0，count可以粗略理解为多数票号超过了其他票号的票数有多少。

拓展：

leetcode 229中求的就是超过三分之一的选票。

可以轻易想到，超过数组三分之一长度的数最多有两个，不可能有三个。
例如[1,1,1,2,2,2,3,3,3]就不存在超过数组三分之一长度的数字
而数组[1,1,1,2,2,2,3,3]存在两个超过数组三分之一长度的数字1、2

做法类似.

Boyer-Moore majority vote algorithm(摩尔投票算法)是一种线性时间复杂度和常数级空间复杂度的算法，用来查找元素序列中的众数。它是用Robert S. Boyer和J Strother Moore两人的名字命名，是一种典型的流算法。

该算法的最简单的形式，查找最多出现的元素，也就是找到一个输入中出现一半以上的重复元素。但是，如果该数不存在的话，算法将检测不到真实结果，但是仍将输出输入元素中的一个元素。 但是，我们可以再次遍历输入序列，计算返回元素出现的次数，以确定它是否真的是众数。

该算法在其局部变量中维护一个临时变量m和一个计数器c，计数器初值为零。 然后我们遍历序列中的每个元素。如果c==0，则m=x;c=1;（其中x表示我们遍历到的元素）。 如果m==x，那么c++，否则c--。 最后返回m即可。

这可以用伪代码表示为以下步骤：

• 初始化一个元素m和一个计算器c=0
• 对于输入序列中的每个元素x
  • 如果i == 0， 那么 m = x 并且 i = 1
  • 如果m == x， 那么c++，否则的话c--
• 返回m

举个例子：

[ 1 1 1 2 2 3 1] m = 0, c = 0
[*1 1 1 2 2 3 1] m = 1, c = 1
[1 *1 1 2 2 3 1] m = 1, c = 2
[1 1 *1 2 2 3 1] m = 1, c = 3
[1 1 1 *2 2 3 1] m = 1, c = 2
[1 1 1 2 *2 3 1] m = 1, c = 1
[1 1 1 2 2 *3 1] m = 1, c = 0
[1 1 1 2 2 3 *1] m = 1, c = 1

实际上这个过程类似于栈。当我们碰到第一个元素1，我们将他压入栈中

stack: 1

接着碰到一系列1，持续压栈，就变成了

stack: 1 1 1

当我们碰到2，此时2和栈顶元素1不同，所以我们需要弹出栈顶元素，同时这个2也不需要压栈。 后面的元素操作同理，最后返回栈顶元素。这样我们只通过m和c两个元素模拟了栈操作。

class Solution 
{
public:
    /*
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    int majorityNumber(vector<int> &nums) 
    {
        int c = 0, m = nums[0];
        for (auto num : nums)
        {
            if (c == 0)
            {
                m = num; ++c;
            }
            else if (m == num) ++c;
            else --c;
        }
        // check if there is a majority
        int counter = 0;
        for (auto num : nums) 
        {
            if (num == m) counter++;
        }
        if (counter < (nums.size() + 1) / 2) return -1;        
        return m;
    }
};

reference:

https://en.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithm

https://helloacm.com/data-structures-algorithms-series-majority-number-boyer-moore-majority-vote-algorithm/