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

题目描述思路实现

题目描述

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

思路

法1

先确定可能是哪个数字： 将数组排序，只可能是最中间的数字在判断该数字出现次数是不是真的超过数组长度一半

法2 利用hashMap存储每个元素的出现次数， 然后判断每个元素出现次数是否超过数组长度一半

实现

法1

import java.util.Arrays; public class Solution { public int MoreThanHalfNum_Solution(int [] array) { //确定可能是哪个数字：排序后在最中间的数字 Arrays.sort(array); int count=0; int n=array.length; for(int i=0;i<n;i++){ if(array[i]==array[n/2]){ count++; } } //再判断该数字出现次数是不是真的超过数组长度一半 if(count>n/2){ return array[n/2]; } else{ return 0; } } }

法2

import java.util.HashMap; public class Solution { public int MoreThanHalfNum_Solution(int [] array) { //HashMap<元素值，元素出现次数> HashMap<Integer,Integer> map=new HashMap<>(); //遍历数组 for(int i=0;i<array.length;i++){ //1.求出所有元素出现的次数 //某元素出现的次数：包装类型，因为hashmap的get方法返回类型不是int!!! Integer count=map.get(array[i]); //若当前遍历的元素再map中还没出现过,就把该元素加入到map，出现次数计为1 if(count==null){ map.put(array[i],1); count=1; } else{ map.put(array[i],++count); } //2.判断每个元素个数是否超过一半 if(count>array.length/2) return array[i]; } return 0; } }