剑指offer第二十八题数组中出现次数超过一半的数字

题目描述

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

方法一：使用快速排序。这种方法不知道能不能用，但是是最简单的...

import java.util.*;
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;}}
}

方法二：使用HashMap。解题时用这个比较好

import java.util.HashMap;
class Solution {public int MoreThanHalfNum_Solution(int [] array) {HashMap<Integer,Integer> hashmap=new HashMap<>();for(int i=0;i<array.length;i++){Integer tmp=hashmap.get(array[i]);if(tmp==null){hashmap.put(array[i], 1);tmp=0;}else{hashmap.put(array[i], tmp+1);}if(tmp+1>array.length/2)return array[i];//而不是hashmap.get(array[i])}return 0;}
}