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

1 题目：
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
2.思路：
方法一：排序的方法
先给数组排序，那么有超过数组长度一半的众数一定在中间也有。
时间复杂度：O(nlongn)
空间复杂度：O(1)

import java.util.Arrays;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
         Arrays.sort(array);//先给数组排序
        int count=0;
        int half=array.length/2;//超过一半的众数一定在中间也有
        for (int i=0;i<array.length;i++)//遍历
        {
            if (array[i]==array[half])
                count++;
        }
        if (count>half)//大于一般，满足条件
            return array[half];
        else
            return 0;
    }
}

方法二：哈希法
采用HashMap记录每个值出现的次数
时间复杂度：O(n)
空间复杂度：O(n)

import java.util.HashMap;//引入HashMap类
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
         HashMap<Integer,Integer>hashMap=new HashMap<>();//此映射所维护的键的类型为整型，所映射值的类型为整型
        for(int i=0;i<array.length;i++){//遍历
            if(hashMap.containsKey(array[i])){//是否存在
                hashMap.put(array[i],hashMap.get(array[i])+1);//映射值加1，记录重复的次数
            }else{
                hashMap.put(array[i],1);//第一次见到
            }
        }
        for(int j=0;j<array.length;j++){//遍历
            if(hashMap.get(array[j])>array.length/2){//是否出现的次数大于数组的一半
                return array[j];
            }
        }
        return 0;
    }
}

方法三：摩尔投票法
遍历数组过程中保存两个值：一个是数组中某一数字，另一个是次数。遍历到下一个数字时，若与保存数字相同，则次数加1，反之减1。若次数=0，则保存下一个数字，次数重新设置为1。由于要找的数字出现的次数比其他数字之和还多，那么要找的数字肯定是最后一次把次数设置为1的数字。（当一个数的出现次数比其他数出现次数的总和还多时，说明这个值是符合条件的）
友情提示：当一个数最终的count>0，并不意味着这个数就符合要求了，比如在数组{1,2,3,4,5,6,7,7,7,8,9,10,10}中，运行完for循环后，最终会记录数字10，并且count为2。这一操作只是尽可能的在找一个出现次数较多的数。因此还需要进行一轮判断if。在第二轮过程中，count才是计数，判断数组中的数是否等于这个找出来的数（因为在不满足的条件的情况下，找出来的这个数只是出现次数较多，而非最多），如果有一半以上等于这个数，就找到，否则，不存在。

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
         int res=array[0];//res记录当前数字类型
         int count=0;//count记录当前数字相较于其他数字的次数
         for(int i=0;i<array.length;i++){
             if(array[i]==res){//同一阵营+1
                 ++count;
             }else{//不同阵营-1
                 --count;
             }
             if(count==0){//消灭，开启新的阵营
                 res=array[i];
                 count=1;
             }
         }
        count=0;
        for(int j=0;j<array.length;j++){//再查询下淘汰出来的数字出现的次数
            if(res==array[j]){
                ++count;
            }
        }
        if(count>array.length/2){//是否真的大于一半
            return res;
        }
        return 0;
    }
}