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

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

抵消法：

如果有大于一半的数，抵消到最后剩下的数即为所求

用preValue记录上一次访问的值，count表明当前值出现的次数，如果下一个值和当前值相同那么count++；

如果不同count–，减到0的时候就要更换新的preValue值了，因为如果存在超过数组长度一半的值，那么最后preValue一定会是该值。

package pers.wmx.practice;

/**
 * @author: wangmingxin03
 * @date: 2020-07-07
 */
public class MoreThanHalfNum {

    public static void main(String[] args) {
        int []arr = {1,2,3,2,2,2,5,4,2};

        int moreThanHalfNum = findMoreThanHalfNum(arr);
        System.out.println(moreThanHalfNum);
    }

    public static int findMoreThanHalfNum(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }

        int preValue = array[0];
        int count = 1;

        for (int i = 1; i < array.length ; i++) {
            if (preValue == array[i]) {
                count ++;
            } else {
                if (count == 1) {
                    preValue = array[i];
                } else {
                    count --;
                }
            }
        }

        //一一抵消，如果存在大于数组长度一半的数，最后剩下的肯定是这个

        //还需要校验一下，最终的数出现次数是否超过数组的一半
        int times = 0;
        for (int i = 0; i < array.length; i++) {
            if (preValue == array[i]) {
                times ++;
            }
        }

        if (times > array.length / 2) {
            return preValue;
        }

        return -1;
    }
}

后面的计数是很有必要的，因为上面的遍历无法保证一定出现次数超过数组长度的一半的数字

为什么不能直接用count 来判断是不是大于数组长度的一半？

比如1，2，2，2，2，2，3，4，5

得到 preValue = 2    count = 2，没办法来判断

因此需要再遍历一变，对preValue计数

转载请注明：汪明鑫的个人博客 » 每周一练（28）