一个算法问题，虽然简单，但是别有趣味。

问题非常简单，已知数组中有一个元素出现次数大于N/2次，其中N为数组长度。求这个元素。

常见解法

首先直观上可以对数组进行排序，然后排序后数组的中位数，就是结果。这种方法复杂度在于排序，为O(n * log(n))。

在数组中元素范围有限，或者元素范围很大，但是可以哈希的话，则可以在数组上进行一次统计计数，那么扫描数组一遍，即可以得到统计结果，然后在统计结果上遍历求解结果。这种方法的复杂度是O(n)的，缺点是需要额外的存储空间，特别是元素范围较大需要哈希，并且出现元素多数不相等的时候，需要O(n)的额外空间。

元素范围有限的情况下，还可以用基数排序，复杂度也是O(n).

上面的两种算法都有些overkill，方法一做了额外的排序，方法二做了额外的统计，这两部分实际上都做了许多的额外操作。

其实对于这个问题，可以随机选择一个元素，然后统计该元素出现次数，如果大于N/2,则返回。检查一个数是否满足N/2，只需要遍历一遍数组即可。这种概率性的算法复杂度是多少呢？

从N个对象中抽取p频次的对象的问题，直到抽中为止。这是一个几何分布问题，呈几何分布的随机变量X的期望值E(X)=1/p。

对于本题，那么期望抽取两次即可以得到结果，看起来非常划算。算法实现在这里majorityElem.169.c

而且以上是考虑从N个对象中抽取，有放回的情况（也就是抽取目标对象，频率保持p不变）。如果设计算法避免重复抽取已知不是目标的对象，那么显然可以进一步提高抽中的概率。期望抽取更少次，就可以得到正确结果。这里避免抽取已经抽过的对象，可以直接在原数组上交换元素就可以完成，不需要额外空间，这里不是重点，就不展开了。这种不放回的抽样方法属于超几何分布。

那么还有更好的算法了吗？有没有只需要常量存储空间，复杂度只有O(n)的确定性算法吗？

这就是本文要介绍的内容。

Moore’s Vote Algorithm

Moore的这个算法，本是非常简单，教授本人对这个直观算法也非常自豪，专门列在自己的`My` Best Ideas页面中。

对于已知必然存在频次大于N/2的对象的情况下，该算法只需要扫描数组一遍，即可得到结果。
算法过程如下：

初始化计数值cnt为0，
扫描数组
    如果cnt为0，那么当前值设为cand，并且cnt设为1.
    如果cnt不为0
        并且当前值和cand相等，则cnt++。
        或者当前值和cand不相等，则cnt--。

这个算法简单到已经可以直接转换为代码了。Moore教授还给出了一个单步运行算法的示例，很直观。
我的实现可以看majorityElem.169.moore.c

假设频次大于N/2的对象值为A，如果cnt等于零，则可以确定在数组已经扫描过的部分，A的出现频率少于等于1/2。(如果A或者任意其他值在已经扫描部分大于1/2，则cnt不能为0)。那么未扫描部分，则A的频率依然是大于等于1/2，问题的规模得以减小，但性质保持不变。具体可以参考论文MJRTY - A Fast Majority Vote Algorithm。

对于确定存在频次大于N/2的对象的情况下，算法到此结束了。
对于不能确定是否存在频次大于N/2的对象的情况下，还需要额外一次数组扫描。对其出现次数进行计数，如果大于N/2,则为结果值，否则没有频次大于N/2的对象。

这个算法只需要2个额外存储空间，并且还可以处理不确定是否存在结果的情况。（概率算法不能够处理这种情况）。而且算法过程异常直观。Moore教授的这篇论文MJRTY - A Fast Majority Vote Algorithm可惜没有出版。

这个问题还可以进一步推广，如何寻找出现频率大于1/3的对象。或者如何寻找出现频率大于1/K(其中K<N)的对象呢？

Moore教授的同事Misra在上述算法的激励下，也在思考这个问题。

Misra’s Algorithm

Misra的这篇论文FindRepeatedElements略微复杂一点，瞄了一眼，没有看懂。。然后找到一份summary，这个summary里面清晰的介绍了算法。

显然出现频率大于1/K的元素最多有K-1个。

这个算法相比Moore的算法扩充在，cand不再是一个值，而是一个规模大小以K-1为上限的候选集合，记为T，对应着集合中的每个元素都有一个计数。当T的元素个数不足K的时候，则加入到T中。当集合T满的时候，且扫描遇到的元素不在集合T中的时候，则对集合中所有对象的计数全部都减一。

好像也不复杂吧？我实现了一个版本majorityElem2.229.c

int *majorityElement(int *nums, int numsSize, int *returnSize) {
    Ctx ctx, *pctx = &ctx;;
    // at most K - 1 elements ocurr greater than [n / K] times.
    initCtx(pctx, K - 1);
    int i, j;
    for (i = 0; i != numsSize; i++) {
        if (pros(pctx, nums[i])) {
        } else if (atnd(pctx, nums[i])) {
        } else {
            cons(pctx);
        }
    }
    int *r = retr(pctx, returnSize);
    deinitCtx(pctx);

    // have to one more pass to verify it really greater than [n / K] times.
    vrfy(nums, numsSize, numsSize / K, r, returnSize);
    return r;
}

我把算法形象地实现为3个动作，pros投票，atnd参加，cons反对票。

- pros，投票，如果扫描对象在候选人中，则对其投票。如果不在候选人中，则投票失败。
- 如果投票失败，那么尝试将当前扫描值加入到候选人。如果候选人已经满了，那么参加(atnd)选举失败
- 如果参加(atnd)失败，则对当前所有候选人投反对票。

完整的算法实现见majorityElem2.229.c。

需要注意的是，这个算法同样需要验证得到候选集合T中的元素的频率是否真的大于1/K。K ！= 2，那么最终符合条件的元素个数最多有 K - 1个。即使有保证存在一个元素频率大于1/K，但是最终扫描得到的候选集合T的元素个数仍然是K - 1，要排除其他的元素，这就需要验证过程啦。

后记

这个算法可以很方便的用于统计计数，下次投票的时候可以用啦。:)

这里的Moore教授还发明了字符串匹配的BM算法。这里的M指的就是他！

链接地址

参考链接

• 几何分布
• 超几何分布
• Moore的示例
• MJRTY - A Fast Majority Vote Algorithm
• FindRepeatedElements

代码

• majorityElem.169.c
• majorityElem.169.moore.c
• majorityElem2.229.c