博耶摩尔最大投票算法在某些情况下会失败吗？

Question

考虑以下包含元素的数组：

0  5  1  5  2  5

该算法不会返回 5 作为多数元素，但在第一遍结束时将 2 视为计数为 0 的多数元素。

这是伪代码：

num1 = array[0], count = 0;
for(int n : array){
    if (n == num1)
        count++;
    else if(count == 0)
        num1 = n;
        count = 1;
    else
        count--;
}

在本次迭代结束时，num1 将包含元素“2”，并且 count 将为 0。 我应该如何让算法返回元素“5”？

Answer 1

虽然5是数组的统计模式，但该数组没有多数元素，因为多数元素的定义是出现超过（数组长度）/2

的元素

[0, 5, 1, 5, 2, 5] --> 长度 = 6

5出现3次；但多数元素的标准是5应该出现3次以上，即4次。