数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{123222542}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

思路一：

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

思路二：

摩尔投票，这个方法我一开始也想到了，但是没有想到这竟然有理论解释，而且是大名鼎鼎的摩尔投票算法。

它的主要步骤是这样的：

初始化两个变量， cand 表示候选人，cnt 表示赞同它的票数。

最后 cand 就是得票超过一半的众数。

思路三：

哈希表，这个方法最简单，用哈希表记录每个数字出现的次数，最后看哪个数字次数超过一半就行了。