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

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

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;
    }
全部评论

相关推荐

ResourceUtilization:你是我见过最美的牛客女孩
点赞 评论 收藏
分享
05-07 17:58
门头沟学院 Java
wuwuwuoow:1.简历字体有些怪怪的,用啥写的? 2.Redis 一主二从为什么能解决双写一致性? 3.乐观锁指的是 SQL 层面的库存判断?比如 stock > 0。个人认为这种不算乐观锁,更像是乐观锁的思想,写 SQL 避免不了悲观锁的 4.奖项证书如果不是 ACM,说实话没什么必要写 5.逻辑过期时间为什么能解决缓存击穿问题?逻辑过期指的是什么 其实也没什么多大要改的。海投吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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