题目描述

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

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

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        
    }
}

 

思路：

其实可以想象一群不同阵营的士兵 去占领一个高低。不同阵营的士兵实力相当，只能一换一。

我们用题目给的数组 array {1,2,3,2,2,2,5,4,2} 来模拟一下，值就是阵营。

遍历数组，读取数组中的值：

array[0]：1号阵营的一个士兵来了， 占领了高地，此时高地有一个 1号阵营的士兵。高地是 1号阵营的。

array[1]：2号阵营的一个士兵来了，和 1号阵营的一个士兵同归于尽了，此时高地没有士兵。 高地是 无人占领的。

array[2]：3号阵营的一个士兵来了， 占领了高地，此时高地有一个 3号阵营的士兵。高地是 3号阵营的。

array[3]：2号阵营的一个士兵来了，和 3号阵营的一个士兵同归于尽了，此时高地没有士兵。 高地是 无人占领的。

array[4]：2号阵营的一个士兵来了， 占领了高地，此时高地有一个 2号阵营的士兵。高地是 2号阵营的。

array[5]：2号阵营的一个士兵又来了， 占领了高地，此时高地有两个 2号阵营的士兵。高地是 2号阵营的。

array[6]：5号阵营的一个士兵来了，和 2号阵营的一个士兵同归于尽了，此时高地有一个 2号阵营的士兵。 高地是 2号阵营的。

array[7]：4号阵营的一个士兵来了，和 2号阵营的一个士兵同归于尽了，此时高地没有士兵。 高地是无人占领的。

array[8]：2号阵营的一个士兵来了， 占领了高地，此时高地有一个 2号阵营的士兵。高地是 2号阵营的。

所以最后高地是 2号阵营的。

我们再遍历一下数组 {1,2,3,2,2,2,5,4,2}，看看2号阵营总共有多少人(既 2 的个数)，

如果 2 的个数大于数组长度的一半，那么 2 就是我们要找的数字。否则就没有要找的数字

 

实现：

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int result = array[0];
        int length = array.length;
        int times = 1;
        for (int i = 1; i < length; i++){
            if(times == 0){
                result = array[i];
                times = 1;
            }else{
                if(array[i] == result){
                    times++;
                }else{
                    times--;
                }
            }
        }
        
        times = 0;
        
        for (int i = 0; i < length; i++){
            if (result == array[i]){
                times++;
            }
        }
        
        if (times*2 <= length){
            return 0;
        }
        return result;
    }
}