剑指offer：数组中有一个数字出现的次数超过数组的一半，请找出这个数字。

方法(1)：用一个count数组记录数组中元素出现的次数(哪个数字出现了，将以这个数字为下标的count数组元素加1，也可以优化以下，即空间开max-min+1这么大，即如果最小的元素出现了，将count下标为0的元素加1，但是当原数组元素范围很大时，这种方法还是比较坑爹).当然这个可以优化到直接用map，元素与次数的映射，而不是自己去统计。

方法(2)：可以将数组进行排序，排好序后，中间那个数便是次数超过一半的数。

方法(3):基于方法(2),我们说如果将数组排好序，那么中间的元素便是出现次数超过一半的数，那么也就是说，我们要找的是中位数，即第n/2大的数，也就是说只要找到第n/2大的数，就是我们要找的出现次数大于一半的数。那么我们可以借助于快排的思想，在数组中找到一个key,使得它大于左边的，小于右边的，并且它的位置位于n/2即可，而这个过程是只要key不是中间位置，就去子区间去找，即需要递归来找。

方法(4)：我们可以分析，一个数出现次数超过一半，那么剩下所有元素出现次数之和小于一半，那么我们遍历数组的时候，保存两个值，一个元素，一个是次数，当遍历到下一个元素时，如果和当前元素相同，就将次数加1，否则将次数减1，如果次数被减到0，那么需要保存下一个数字并且将此时的次数置为1，这样下去，最后保存的数字一定是出现次数最多的那个数字（因为次数小于一般的其它元素将会抵消一部分次数大于一半的，但是次数大于一半的那个数字终究会剩一部分出来，这部分至少是1）。

方法(5):遍历数组，每次删除两个不相同的元素，直到剩下的元素中没有相同的元素你，就是我们要找的出现次数超过一半的。（因为两个不相同的元素有两种可能，第一种是两个都是次数小于一半的，那么刚好可以剩下次数多余一半的，第二种是一个是小于一半的，一个是多余一半的，那么多余一半的最终会剩一部分数据出来，这部分数据至少是1个，原因和上面一样，就是它次数多余一半，要抵消也最多抵消一半，肯定还会剩下）