数组中出现次数超过一半的数
数组中出现次数超过一半的数字
http://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163
思路分析：
解法一：通过hashMap去做，第一遍遍历整个数组，将数组中的每一个值录入到hashMap的key中去，value为次数，重复的key则使其value增加1，第二次遍历 在hashMap中取出数组的每一个数值对应的次数 大于一半的则返回。
解法二：假如数组中存在众数，那么众数一定大于数组的长度的一半。思想就是：如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。
import java.util.*;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int length = array.length;
if(array == null || length == 0){
return 0;
}
HashMap<Integer,Integer> hashMap = new HashMap(length);
for(int i = 0; i < length; i++){
if(hashMap.containsKey(array[i])){
hashMap.put(array[i],hashMap.get(array[i])+1);
}else{
hashMap.put(array[i],1);
}
}
for(int i = 0; i < length; i++){
if(hashMap.get(array[i]) * 2 > length){
return array[i];
}
}
return 0;
}
} import java.util.*;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int length = array.length;
if(array == null || length == 0){
return 0;
}
int result = 0;
int count = 0;
for(int i = 0; i<length; i++){
if(count == 0){
result = array[i];
count = 1;
}else if(array[i] == result){
count++;
}else{
count--;
}
}
count = 0;
for(int i = 0; i < length; i++){
if(result == array[i]){
count++;
}
}
if(count * 2 > length){
return result;
}
return 0;
}
} 
查看30道真题和解析
