题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
分析：找数组中出现次数超过一半的数字，我们一半可以采用两种方法，一是使用快排，对数组进行排序，然后直接输出排序数组中间位置的数。第二种是使用HashMap<Integer,Integer>,key是数组中的数字，value为其在数组中出现的次数，顺序扫描数组，记录下数组出现的次数，输出大于数组长度一半的value值对应的key值。
第一种方法代码很简单，此处不表，第二种方法的代码如下：
1 import java.util.ArrayList;
2 import java.util.Arrays;
3 import java.util.Collection;
4 import java.util.HashMap;
5 import java.util.Set;
6
7 public class Solution {
8 public int MoreThanHalfNum_Solution(
int [] array) {
9 if(array==
null||array.length==
0){
10 return 0 ;
11 }
12 if(array.length==
1){
13 return array[
0] ;
14 }
15 int most=
0 ;
16 HashMap<Integer,Integer> m =
new HashMap<Integer,Integer>
() ;
17 for(
int i =
0 ; i < array.length ;i++
){
18 if(!
m.containsKey(array[i])){
19 m.put(array[i],
1) ;
20 }
21 else{
22 int temp = m.
get(array[i]);
23 m.put(array[i], temp+
1) ;
24 }
25
26 }
27 Set<Integer> a =
m.keySet() ;
28 for(
int temp : a){
29 if(m.
get(temp)>(array.length/
2)){
30 most =
temp ;
31 }
32 }
33 return most ;
34 }
35 }
转载于:https://www.cnblogs.com/huntertoung/p/4803147.html
