笔试题：找出数组中出现次数超过数组大小一半的整数

summary

:

今天去参加人人的笔试，好多人，好多大神，题目也很难。倒数第二题是这样的。

题目

现在有一个长度为n的数组a，里面有超过一半的整数为一个定值，在不用排序，不开辟新 数组的情况下，用最快的算法找出来这个数， int find(int *a, int n) 。

分析

唉，纠结了好久没做出来，果然算法不行的人是要被虐的，没办法，只能多练了。搜了一 下，原来这题也是千年的老题，看了 这里 的分析，才暗暗觉得人家的算法的高明。

只需要两个变量，一个记录当前值，一个是计数器。初始的时候，当前值为第一个元素， 计数器为1。然后遍历整个数组，遇到和当前值不同的数，计数器减1，相同则加1，如果 计数器等于0,则说明这个数不是目前出现次数最多的数，则有可能不是出现次数超过数组 大小的一半的那个数，这时候就要把当前值赋值为遍历到的这个值，计数器重新赋值为1。

更新：之前想的不够深入，看了 这篇文章 之后明白了。原来算法是这样的。

设出现次数超过数组大小的一半的这个数为a，那我把前面相邻的两个不同的数删掉之后， 不管这两个数其中一个是不是a，剩下的数组中，a的出现次数也超过一半。继续删除下去， 最后剩下的一定是a（一个或者多个）。

我的代码

::: {.code-include lexer="cpp"} ./find-integer-appears-more-than-half-of-the-array.cpp :::

使用了Boost的单元测试框架，链接的时候要加上 -lboost_unit_test_framework 参数。