28.数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 法1.将数组元素进行一个排序，数组元素排序后，如果符合条件的数存在，则一定是数组中间那个数。（比如：1，2，2，2，3；或2，2，2，3，4；或2，3，4，4，4等等） 这种方法虽然容易理解，但由于涉及到快排sort，其时间复杂度为O(NlogN)并非最优；
import java.util.Arrays; public class Solution { public int MoreThanHalfNum_Solution(int [] array) { Arrays.sort(array);// 排序，取数组中间那个数 int count=0; for(int i=0;i<array.length;i++){ if(array[i]==array[array.length/2]){ count++; } } if(count>array.length/2){ return array[array.length/2]; }else{ return 0; } } }法2.用hashMap
import java.util.HashMap; import java.util.Map; public class Solution { public int MoreThanHalfNum_Solution(int [] array) { if(array.length==0||array==null) return 0; Map<Integer,Integer> map=new HashMap<Integer,Integer>(); //containsKey方法判断Map集合对象中是否包含指定的键名。 //如果Map集合中包含指定的键名，则返回true，否则返回false。 for(int i=0;i<array.length;i++){ if(map.containsKey(array[i])){ int count=map.get(array[i]);//get方法由Key来获取相应元素的Value map.put(array[i],++count);//put向集合添加key和value， }else{ map.put(array[i],1);//这一步说明没有重复，只出现了一次 } } //遍历整个map，entry相当于map里面的一个键值对， //可用通过entry获取key和value for(Map.Entry<Integer,Integer> entry:map.entrySet()){ //entrySet().以map集合中的Key=Value的形式返回到set集合中。 if(entry.getValue()>array.length/2) return entry.getKey(); } return 0; } }