题目:找出数组中出现次数超过一半的数,现在有一个数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数。

出题人:阿里巴巴新零售技术质量部

参考答案

遍历数组的同时用Object来储存每个元素出现的个数,每次遍历都跟max比较

参考代码

const arr =[1,2,3,4,5,6,7,8,89,9,9,9,9,99];

const maxNumObj =(arr)=>{
    return arr.reduce((obj,cur)=>{
        if(!obj['max']){
            obj['max']=arr[0];
        }
        obj[cur] = ++obj[cur]||1;
        if(obj[cur]>obj['max']){
          obj['max'] = obj[cur]
        }
        return obj;
    },{})['max'];
}