Question

题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

看到这道题很多应聘者就会想要是这个数组是排序的数组就好了。如果是排好序的数组，那么我们就能很容易统计出每个数字出现的次数。题目给出的数组没有说是排序的，因此我们需要先给它排序。排序的时间复杂度是O（nlogn）。最直观的算法通常不是面试官满意的算法，接下来我们试着找出更快的算法。

解法一：基于Partition函数的O（n）算法

如果我们回到题目本身仔细分析，就会发现前面的思路并没有考虑到数组的特性：数组中有一个数字出现的次数超过了数组长度的一半。如果把这个数组排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。也就是说，这个数字就是统计学上的中位数，即长度为n的数组中第n/2大的数字。我们有成熟的O（n）的算法得到数组中任意第k大的数字。

这种算法是受快速排序算法的启发。在随机快速排序算法中，我们先在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小数字都排在它的左边，比选中的数字大的数字都排在它的右边。如果这个选中的数字的下标刚好是n/2，那么这个数字就是数组的中位数。如果它的下标大于n/2，那么中位数应该位于它的左边，我们可以接着在它的左边部分的数组中查找。如果它的下标小于n/2，那么中位数应该位于它的右边，我们可以接着在它的右边部分的数组中查找。这是一个典型的递归过程，可以用如下代码实现：

上述代码中的函数Partition是完成快速排序的基础。我们在本书的2.4.1节详细讨论了这个函数，这里不再重复。

在面试的时候，除了要完成基本功能即找到符合要求的数字之外，还要考虑一些无效的输入。如果函数的输入参数是一个指针（数组在参数传递的时候退化为指针），就要考虑这个指针可能为NULL。下面的函数CheckInvalidArray用来判断输入的数组是不是无效的。题目中说数组中有一个数字出现次数超过数组长度的一半，如果输入的数组中出现频率最高的数字都没有达到这个标准那该怎么办？这就是我们定义了一个CheckMoreThanHalf函数的原因。面试的时候我们要全面考虑这些情况，才能让面试官完全满意。下面的代码用一个全局变量来表示输入无效的情况。更多关于出错处理的讨论，详见本书3.3节。

解法二：根据数组特点找出O（n）的算法

接下来我们从另外一个角度来解决这个问题。数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。

下面是这种思路的参考代码：

和第一种思路一样，我们也要检验输入的数组是不是有效的，这里不再重复。

解法比较

上述两种算法的时间复杂度都是O（n）。基于Partition的算法的时间复杂度的分析不是很直观，本书限于篇幅不作详细讨论，感兴趣的读者可以参考《算法导论》等书籍的相关章节。我们注意到在第一个解法中，需要交换数组中数字的顺序，这就会修改输入的数组。我们是不是可以修改输入的数组呢？在面试的时候，我们可以和面试官讨论，让他明确需求。如果面试官说不能修改输入的数组，那就只能采用第二种算法了。

源代码：

本题完整的源代码详见29_MoreThanHalfNumber项目。

测试用例：

- 功能测试（输入的数组中存在一个出现次数超过数组长度一半的数字，输入的数组中不存在一个出现次数超过数组长度一半的数字）。

- 特殊输入测试（输入的数组中只有一个数字、输入NULL指针）。

本题考点：

- 考查对时间复杂度的理解。应聘者每想出一种解法，面试官都期待他能分析出这种解法的时间复杂度是多少。

- 考查思维的全面性。面试官除了要求应聘者能对有效的输入返回正确的结果之外，同时也期待应聘者能对无效的输入作相应的处理。