题目
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
分析
一个数组，我们很容易想到的是，直接对数据进行升序排列，而排序算法最好的平均时间复杂度是O(nlogn)。还有没有更快的算法呢？假如我们去遍历数组，然后每次都记录某个值出现的次数，这个值出现一次就增加1。很自然的想到hashmap这种数据结构。其实这就是一种键值对，我们可以使用key来存储数组中元素的值，使用value来存储出现的次数，每遍历一个数之后，就更改对应的value值。
代码
综上分析，代码如下：
import java.util.*;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
HashMap <Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0; i < array.length; i++){
if(!map.containsKey(array[i])){
map.put(array[i],1);
}else{
int count = map.get(array[i]) + 1;
map.put(array[i],count);
}
}
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()){
Map.Entry entry = (Map.Entry)iter.next();
Integer count = (Integer)entry.getValue();
Integer key = (Integer)entry.getKey();
if(count > (array.length / 2)){
return key;
}
}
return 0;
}
}
其中，需要注意的是Iterator iter = map.entrySet().iterator();这是一个迭代器，它将hashmap类型的数据转换成集合类型，就可以用while进行遍历了。
其他解法
还有一种解法是根据数组的特点。一个数字出现的次数超过数组的一半，那么这个数字出现的次数要比其他所有数字出现的次数之和还要大。所以我们只保留两个变量， 一个变量是数组中的数字，一个是次数。当遍历到一个数，和前面一个数的个数相同时，次数+1，如果不相同，那么次数-1.如果次数为0，临时保存的数字就改变成当前 正在遍历的这个数。所以，我们要找的数字，一定是最后一次把次数设置为1的数字。
过程如下图所示：
综上分析，代码如下：
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int count = 0;
int temp = 0;
for(int i = 0; i < array.length; i++){
if(array[i] == temp){
count ++ ;
}else if(count > 0){
count --;
}else{
count = 1;
temp = array[i];
}
}
// 还要验证
count = 0;
for(int j = 0; j < array.length ;j++){
if(array[j] == temp)
count ++;
}
return count > array.length/2 ? temp : 0;
}
}
