数组中出现次数超过一半长度的数字

数组中出现次数超过一半的数字

http://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163

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

用HashMap实现

import java.util.HashMap;
import java.util.Map;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array==null || array.length==0) return 0;
        if(array.length==1) return array[0];//只有一个元素的数组是容易代码遗漏的地方
        int key = array.length/2;
        int count;
        Map<Integer, Integer> visit = new HashMap<>();
        for(int i=0; i<array.length; i++){
            if(!visit.containsKey(array[i])){
                visit.put(array[i], 1);
            }else{
                count=visit.get(array[i]);
                if(count+1>key){
                    return array[i];
                }
                visit.remove(array[i]);
                visit.put(array[i], count+1);
            }
        }
        return 0;
    }
全部评论

相关推荐

frutiger:逆天,我家就安阳的,这hr咋能说3k的,你送外卖不比这工资高得多?还说大厂来的6k,打发叫花子的呢?这hr是怎么做到说昧良心的话的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务