常见算法之3---数组中出现次数超过一半的数字

题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。

示例 int[] a = {1,2,4,2,3,2,5,2,2} 输出：2

方案1：若是数组为排好序的，则中间位置的那个数，一定是为所求。

所以可以先将数组排序，然后直接输出中间的那个数。平均的排序时间为O(nlogn)。

方案2：不排序，依次统计每一元素的次数，使用哈希表。时间为遍历一次数组的时间加上遍历一次哈希表，找到其中最大的次数的时间。并且，哈希表还要占用一定的空间。

方案3：我们应该注意到，要找的数字出现的次数比其他所有数字出现次数的和还要多。因此在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1。如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，那么要找的数字肯定是最后一次保存的数字。

代码：

   int find(int[] a) {
       int num = a[0];  //记录数据，先赋予第一个元素
       int count = 1;   //统计次数
       int i = 0;       //用于遍历

       while (i < a.length - 1) {

            if (a[i + 1] == num)    
                count++;
             else
                count--;

             if (count == 0)       //若为0，则后移
                num = a[i + 2];
             i++;
       }