数组中出现次数超过一半的数字

题目描述：

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

解题思路

方法一：

可以将数组进行排序，然后从前到后统计每个数字出现的次数，进行判断，此时时间复杂度按照排序算法的时间复杂度为O(nlogn).

方法二：

根据题目的描述，求出现次数超过数组长度一半的数字，那么该数字在排序好的数组中应该位于中间位置。
那么可以利用快排partiition的过程，选取一个数，将数组分成小于部分，大于部分，如果该数的下标等于中间位置，那么这个数就是所要求的数。
如果该数的下标大于中间位置，将下标减一，在左边部分进行递归，如果该数的下标小于中间位置，将下标加一，在右边部分进行递归。直到该数的下标等于中间位置，从而得到该数。
此外还需要判断一下该数的次数是否大于数组长度的一半，因为可能虽然该数处在数组的中间位置了，但是长度并没有超过数组长度的一半。

方法三：

利用数组的特性，根据题目的描述，该数字出现的次数比其他所有数出现的次数加起来都大。可以从头进行遍历，将第一个数记录下来，次数记为1，在遍历的过程中，遇到相同的数次数就加一，不同的就减一，如果次数等于0 了，就重新记录当前遍历到的数。遍历一遍数组后，剩下的记录到的数就是所要求的数。
同样进行一下判断该数的次数是否大于数组长度的一半，因为可能虽然该数处在数组的中间位置了，但是长度并没有超过数组长度的一半。