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

题目描述

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

解题思路

我们设定一个临时数字 tmp：

• 如果下一个数字与 tmp 相同，则 length++；

• 如果不相同，则 length--；

• 如果 length 已经等于-1，说明在目前为止，tmp 的数目没有达到一半，将 tmp 替换为本值，重置 length=1。

因为数字出现次数要超过数组的一半，如果存在，最后该数字 length 一定大于 1。但是也有不存在的可能，此时的 tmp 就是最后几个数字，所以要再遍历一遍数组，查看该数字出现次数。

代码

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if (array == null || array.length == 0)
            return 0;
        int tmp = array[0];
        int length = 1;
        for (int i = 1; i < array.length; i++) {
            if (array[i] == tmp)
                length++;
            if (array[i] != tmp)
                length--;
            if (length == -1) {
                tmp = array[i];
                length = 1;
            }
        }
        length = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == tmp)
                length++;
        }
        if (length > array.length/2)
            return tmp;
        return 0;
    }
}