出现次数超过一半的数（面试题）

题目描述

数组中有一个数出现的次数超过了数组长度的一半，找出这个数。

分析与解法

因为不确定给定的数组是无序还是有序的，所以要分情况讨论。

解法一：排序

如果给定的数组是无序的，那么可以先对数组进行排序（至于排序方法可选取最常用的快速排序）。排完序后遍历数组，在遍历整个数组的同时统计每个数的出现次数，然后把那个出现次数超过一半的数直接输出，题目便算解答完了。总的时间复杂度为O(nlogn+n)。

但是，如果给定的数组是有序的，或者经过排序后把无序的数组变成有序的之后，是否还需要再遍历一次数组，以统计每个数出现的次数呢？

实际上，如果某个数在数组中的出现次数超过一半，那么在已经排好序的数组索引的 n/2 处（从零开始编号）就一定是要我的这个数。因此，对整个数组排完序之后，只需要直接输出数组中的第n/2处的数即可，这个数即是整个数组中出现次数超过一半的数，总的时间复杂度由于少了最后一次整个数组的遍历，而降到O(nlogn)。

然而，时间复杂度从O(nlogn+n)降到O(nlogn)并无本质上的改变，我们需要找到一种更有效的思路或方法。

解法二：散列表

通常来说，要想降低时间复杂度，有这么几个思路可以选择。

·减少不必要的操作，比如解法一中数组排完序后可以直接输出第n/2处的那个数，不必再统计每个数的出现次数。

·以空间换时间，比如借助散列表达到快速映射的目的。

应根据问题本身的特性使用对应的技巧。比如在KMP算法中，通过对模式串的预处理求解出next数组，而后匹配失败时直接查next数组便可得到下一次匹配的位置。

针对以空间换时间，我们自然而然想到了查找时间复杂度为O(1)的散列表。首先用散列表完成数组中每个数出现次数的统计，其中，散列表的键为数组中的数，值为该数出现的次数。这样，利用散列表完成统计后，如果需要找出那个出现次数超过一半的数，直接遍历整个散列表，然后输出该数即可。

构照叙列表后，查一次的时间复杂度为O(1)，遍历一遍查询n次，则总的时间复杂度为O(1)。但是，散列表的方法需要O(n)的空间开销，且要设计散列函数，还有没有更好的办法呢？

解法三：每次删除两个不同的数

根据这个问题本身的特殊性，可以试着这么考虑，通过每次删除两个不同的数（不管是不是我们要查找的那个出现次数超过一半的数），在剩下的数中，我们要查找的数的出现次数仍将会超过剩余总数的一半。通过不断重复这个过程，不断排除掉其他的数，最终找到那个出现次数超过一半的数。总的说来，时间复杂度只有O(n)，空间复杂度为O(1)，免去了排序，也避免了O(n)的空间开销。

举个简单的例子，如数组a[5]={0, 1, 2, 1, 1}。很显然，若要找出数组a中出现次数超过一半的数，这个数便是1。通过一次性遍历整个数组，然后每次删除不相同的两个数，过程简单表示如下。

（1）给定序列0, 1, 2, 1, 1。

（2）删除不相同的两个数0和1，序列变为2, 1, 1。

（3）最后再删去两个不同的数2和1，序列变为1。

（4）最终1即为所要找的结果。

解法四：记录两个值

更进一步，我们可以在遍历数组的时候保存两个值：一个是candidate，用来保存数组中遍历到的某个数；另一个是nTimes，表示当前数的出现次数，其中nTimes初始化为1。当遍历到数组中下一个数的时候：

·如果下一个数与之前candidate保存的数相同，则nTimes加1；

·如果下一个数与之前candidate保存的数不同，则nTimes减1；

·每次当出现次数nTimes变为0后，用candidate保存下一个数，并把nTimes重新设为1。

·直到遍历完数组中的所有数为止。

举个例子，假定数组为{0, 1, 2, 1, 1}，按照上述思路执行的步骤如下。

（1）开始时，candidate保存数0，nTimes初始化为1。

（2）然后遍历到数字1，与数0不同，则nTimes减1变为0。

（3）因为nTimes变为了0，故candidate保存下一个遍历到的数2，且nTimes被重新设为1。

（4）继续遍历到第4个数1，与之前candidate保存的数2不同，故nTimes减1变为0。

（5）因nTimes再次被变为了0，故让candidate保存下一个遍历到的数1，且nTimes被重新设为1。

（6）最后返回的就是最后一次把nTimes设为1的数1。

思路清楚了，完整的参考代码如下：

// a代表数组，length代表数组长度
int FindOneNumber(int* a, int length)
{
         int candidate = a[0];
         int nTimes = 1;
         for (int i = 1; i < length; i++)
         {
                 if (nTimes == 0)
                 {
                         candidate = a[i];
                         nTimes = 1;
                 }
                 else
                 {
                         if (candidate == a[i])
                        {
                                 nTimes++;
                         }
                         else
                         {
                                 nTimes--;
                         }
                 }
         }
         return candidate;
}

针对数组{0, 1, 2, 1, 1}执行上述程序后，candidate和nTimes等相关变量的变化如表4-1所示。

表4-1

举一反三

出现次数刚好是一半的数

有n个数，其中有一个数刚好出现一半次数，要求在线性时间内求出这个数。

点评：如果是刚好出现一半，如此例的{0, 1, 2, 1}，开始时，candidate保存数0，nTimes初始化为1；遍历到1时，与candidate不同，nTimes减为0；遍历到2时，因nTimes为0，故candidate更新为2，nTimes重新设为1；遍历到1后，与之前candidate保存的数2不同，则nTimes减为0；最终返回candidate所保存数（2）的下一个数1。

问题扩展

给定一个有限集合U，S1, S2,…, Sn都是U的非空子集，且它们满足任意多个集合的并集仍然在这些集合里。请证明：一定存在某一个元素，存在于至少一半的集合里。

点评：1999年，有人证明了存在一个元素在至少n/log2n个集合里出现。但离本题的证明目标还差很远。