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

题目描述

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

要求

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32M，其他语言64M
本题知识点： 数组

题解

1. 根据题目意思，利用数据的特性，一半以上都是相同数字，那么对其中任意不相同的两个数进行一一抵消，最后肯定能得到一个数

2. 最后再遍历该数在数组中出现的次数，看是否大于数组长度的一半即可。

3. 用now记录当前的值，count表明当前值出现的次数，如果下一个值和当前值相同那么count++；如果不同count--，说明有一对不相同的两个数抵消了，减到0的时候就要更换新的now值了。因为如果存在超过数组长度一半的值，那么最后now一定会是该值。

    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length == 0) {
            return 0;
        }
   
        int count = 1, now = array[0];
        for(int i = 1;i< array.length ;i++){
            if(array[i] != now) {
                count--;
            } else {
                count++;
            }
   
            if(count == 0) {
                now = array[i];
                count++;
            }
        }
   
        count = 0;
        for (int value : array) {
            if (value == now) {
                count++;
            }
        }
   
        if(array.length/2 < count) {
            return now;
        } else {
            return 0;
        }
    }