题解 | #数组中出现次数超过一半的数字#

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

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

就问有没有更拉胯的代码解法,挑战下限,1%+1%

import java.util.HashSet;
import java.util.ArrayList;
public class Solution {
  public int MoreThanHalfNum_Solution(int [] array) {
        //先遍历一遍得到数字种类,用set做判定
        HashSet type_set=new HashSet();
        ArrayList type=new ArrayList();
        for(Integer x:array){
            if(type_set.add(x)){
                type.add(x);
            }
        }
        //再开一个与种类等长的数组,索引匹配,记录出现次数
        ArrayList num=new ArrayList();
        for (int i = 0; i <type.size() ; i++) {
            num.add(0);
        }
        //再遍历一次种类数组,得到次数数组
        for (int i = 0; i <type.size(); i++) {
            for (int j = 0; j < array.length; j++) {
                if(array[j]==type.get(i)){
                    num.set(i,num.get(i)+1);
                }
            }
        }
        //遍历次数数组,取出最大次数对应索引
        int max=0;
        int type_index = 0;
        int most_type = 0;
        for (int i = 0; i <num.size() ; i++) {
            if(num.get(i)>=max){
                max=num.get(i);
                type_index=i;
            }
        }
        //判定次数是否大于原数组长度一半,大则返回该索引对应的种类
        if (max>array.length/2){
            most_type=type.get(type_index);
        }
        return most_type;
    }
}
全部评论

相关推荐

05-07 17:58
门头沟学院 Java
wuwuwuoow:1.简历字体有些怪怪的,用啥写的? 2.Redis 一主二从为什么能解决双写一致性? 3.乐观锁指的是 SQL 层面的库存判断?比如 stock > 0。个人认为这种不算乐观锁,更像是乐观锁的思想,写 SQL 避免不了悲观锁的 4.奖项证书如果不是 ACM,说实话没什么必要写 5.逻辑过期时间为什么能解决缓存击穿问题?逻辑过期指的是什么 其实也没什么多大要改的。海投吧
简历中的项目经历要怎么写
点赞 评论 收藏
分享
流浪的神仙:无恶意,算法一般好像都得9硕才能干算法太卷啦
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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