题目:找出数组中出现次数超过一半的数,现在有一个数组,已知一个数出现的次数超过了一半,请用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'];
}
- 原文作者:知识铺
- 原文链接:https://geek.zshipu.com/post/%E9%9D%A2%E8%AF%95/03.%E7%99%BE%E5%BA%A6%E7%AF%87/3.4.8-%E6%89%BE%E5%87%BA%E6%95%B0%E7%BB%84%E4%B8%AD%E5%87%BA%E7%8E%B0%E6%AC%A1%E6%95%B0%E8%B6%85%E8%BF%87%E4%B8%80%E5%8D%8A%E7%9A%84%E6%95%B0%E7%8E%B0%E5%9C%A8%E6%9C%89%E4%B8%80%E4%B8%AA%E6%95%B0%E7%BB%84%E5%B7%B2%E7%9F%A5%E4%B8%80%E4%B8%AA%E6%95%B0%E5%87%BA%E7%8E%B0%E7%9A%84%E6%AC%A1%E6%95%B0%E8%B6%85%E8%BF%87%E4%BA%86%E4%B8%80%E5%8D%8A%E8%AF%B7%E7%94%A8On%E7%9A%84%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%9A%84%E7%AE%97%E6%B3%95%E6%89%BE%E5%87%BA%E8%BF%99%E4%B8%AA%E6%95%B0/
- 版权声明:本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可,非商业转载请注明出处(作者,原文链接),商业转载请联系作者获得授权。
- 免责声明:本页面内容均来源于站内编辑发布,部分信息来源互联网,并不意味着本站赞同其观点或者证实其内容的真实性,如涉及版权等问题,请立即联系客服进行更改或删除,保证您的合法权益。转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。也可以邮件至 sblig@126.com