[数据结构与算法]找出数组中超过一半的数字（java）

问题描述：

代码如下：（1）可以使用排序的算法，然后直接返回
（2）使用map，扫描一次即可
（3）使用经典方法之消除法

import java.util.*;
public class Seventh {
    //找出数组中超过一半的数字
    //方法一：将数组进行排序，然后返回数组中间的值
    public static int solve(int[] a){
        Arrays.sort(a);
        return a[a.length/2];
    }
    //方法二：利用hash进行解决
    public static int solve1(int[] a){
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i <a.length ; i++) {
            if (map.containsKey(a[i])){//如果已经包含这个数字，则将value值++
                int temp=map.get(a[i]);
                temp++;
                if (temp>a.length/2) return a[i];
                map.put(a[i],temp);
            }else {
             map.put(a[i],1);
            }
        }
        int res=-1;//记录最终结果
        for (Map.Entry<Integer, Integer> entry:map.entrySet()) {//对map进行遍历，寻找value大于长度一半的数字
               if (entry.getValue()>a.length/2) res=entry.getKey();
        }
        return res;
    }
    //方法三 消除法(不同的元素采用两两消除法)
    public static int solve3(int[] a){
        int target=a[0];//把第一个作为消除的对象
        int count=1;
        for (int i = 1; i <a.length ; i++) {
            if (count==0){//需要重新定目标
               target=a[i];
               count=1;
               continue;
            }
            if (a[i]!=target) count--;
            else count++;
        }
        return target;
    }
    public static void main(String[] args) {
        int[] a={0,1,0,1,0};
        System.out.println(Arrays.toString(a));
        System.out.println(solve(a));
        System.out.println(solve1(a));
        System.out.println(solve3(a));
    }
}

结果如下：