题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如，输入一个长度为9的数组{1，2，3，2，2，2，5，4，2}。由于数字2再数组中出现了5次，超过数组长度的一半，因此输出2。
初步思路：将数组中的元素进行排序，统计每个数字出现的次数，然后找出出现次数超过一半的那个数字。这样的话排序的时间复杂度将是O(nlogn)。
在面试中，这样的时间复杂度可能不会令面试官满意，是否存在速度更快的算法呢？
解法：数组中有一个数字出现的次数超过了数组的一半等价于它出现的次数要比其他所有的数字出现的次数之和都要大。我们在遍历数组的时候保存两个值：一个是数组中的一个数字；另一个是次数。如果我们遍历的下一个数字和我们之前的数字一样，则次数+1；如果不一样，则次数-1。这样的话，我们的算法的时间效率则是O(n)。
基本实现
但是，我们还要考虑到一些无效的输入。数组是否有效？数组中是否存在出现次数超过数组长度一半的数字？这些都要考虑到。
有效性判断方法
这样才算一个完整的实现。
完整代码
具体请参考《剑指Offer》。
