【Java编程题】在数组中找到出现次数大于一半的数

我会带着你远行 2023-07-07 05:59 1阅读 0赞

题目描述：

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

**实现方法1：利用中位数**

第一步：对数组先进行排序

第二步：如果出现次数要大于数组的一半，则数组下标为数组长度一半的这个数一定为要求的这个数

第三步：从前到后统计这个数字出现的次数，如果出现的次数大于数组长度的一半，则返回这个数字，否则，返回0

代码：

import java.util.Arrays;
    public class Main{
        public int MoreThanHalfNum_Solution(int [] array){
            Arrays.sort(array);
            int count=0;
            int length=array.length;
            for(int i=0;i<length;i++){
                if(array[i]==array[length/2]){
                    count++;
                }
            }
            if(count>length/2){
                return array[length/2];
            }else{
                return 0;
            }
        }
    }

**实现方法2：利用HashMap**

第一步：利用HashMap中的key去记录数组中的数字，value记录该数字出现的次数

第二步：遍历map集合，如果有value大于数组的一半，那么就返回该value所对应的key值

注意：在此方法中，要熟练掌握map的各个方法使用

代码：

import java.util.*;
    public class Main {
        public int MoreThanHalfNum_Solution(int [] array) {
            int length=array.length;
            Map<Integer,Integer> map=new HashMap<>();
            for(int i=0;i<length;i++){
                int count=map.getOrDefault(array[i],0);
                map.put(array[i],count+1);
            }
            for(Map.Entry<Integer,Integer> m:map.entrySet()){
                int key=m.getKey();
                int valve=m.getValue();
                if(valve>length/2){
                    return key;
                }
            }
            return 0;
        }
    }

**注意：在写力扣、牛课题时，如果引用到了Java中的包，一定要在开头写出。**