（java版剑指offer）JZ39 数组中出现次数超过一半的数字

https://uploadfiles.nowcoder.com/images/20220303/523247478_1646306407396/D2B5CA33BD970F64A6301FA75AE2EB22

//方法一：排序+统计

import java.util.Arrays;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //先排序
        //循环遍历
            //统计连续几个相同数字的个数
                //超过半数则返回值
            //没超过半数，则继续循环
        
        Arrays.sort(array);    //先排序
        
       int count = 1;
       int num = array[0];
        
       for(int i=1; i<array.length; i++){
           //统计连续几个相同数字的个数
           if(array[i] == num){
               count++;
               //超过半数则返回值
               if(count>(array.length>>1))
                   return num;
           }
           //没超过半数，则继续循环
           else{
               num = array[i];
               count = 1;
           }
       }
        return num;
        
    }
}

//方法二：hashmap

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //使用map(key, value)来做
        //类似新建一个数组，以原数组的值为下标，以该下标存放的值是个数
        //新建一个HashMap对象
        //然后遍历数组
            //将数组的元素作为map中的key, 元素的个数count作为map中的value
            //统计count个数是否大于半数以上
                //大于半数，输出结果
                //否则就重新循环
        Map<Integer, Integer> map = new HashMap();
        
        for(int i=0; i<array.length; i++){
            // 哈希表的getOrDefault(key, default)方法，
            //是在哈希表中搜索是否存在该方法参数列表中的key值，
                //如果存在该key值，则返回哈希表中该key值对应的vakue值；
                //如果不存在，则返回该方法参数列表中的default值
            //开始map中没有array[i], 默认返回值是0
            int count = map.getOrDefault(array[i], 0) + 1;    
            //大于半数，输出结果
            if(count>(array.length>>1))
                return array[i];
            //否则就重新循环
            else{
                map.put(array[i], count);
            }
        }
        return 0;
        
    }
}

//方法三：遍历数组
//for(元素类型int 元素变量x : 遍历对象obj)

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //使用map(key, value)来做
        //类似新建一个数组，以原数组的值为下标，以该下标存放的值是个数
        //新建一个HashMap对象
        //然后遍历数组
            //将数组的元素作为map中的key, 元素的个数count作为map中的value
            //统计count个数是否大于半数以上
                //大于半数，输出结果
                //否则就重新循环
        Map<Integer, Integer> map = new HashMap();
        
        for(int x : array){
            // 哈希表的getOrDefault(key, default)方法，
            //是在哈希表中搜索是否存在该方法参数列表中的key值，
                //如果存在该key值，则返回哈希表中该key值对应的vakue值；
                //如果不存在，则返回该方法参数列表中的default值
            //开始map中没有array[i], 默认返回值是0
            int count = map.getOrDefault(x, 0) + 1;    
            //大于半数，输出结果
            if(count>(array.length>>1))
                return x;
            //否则就重新循环
            else{
                map.put(x, count);
            }
        }
        return 0;
    }
}