首页 > 编程语言 > 详细

找到数组中频次大于1/k的数

时间:2019-06-10 13:10:48      阅读:134      评论:0      收藏:0      [点我收藏+]

Majority Number III

给定一个数组(长度为L),找到所有出现频次大于1/k的数字。

  我们主要使用摩尔投票法(Voting Algorithm)结合Map的数据结构解决此问题。其时间复杂度O(n),空间复杂度O(k)。

  主元素数量大于数组长度的1/k,因此有k-1一个候选人(Candidate),通过loop整个数组两次得到答案,遍历第一次找有可能的候选人,第二次统计这些候选人出现的频次。  

  当数组长度L小于k时,直接对所有出现的数字进行统计得到结果。

  当数组长度L大于等于k时,建立一个以<candidate, counter>的容量为k-1的Map,遍历数据进行统计,如果Map的容量未满k-1或者存在candidate的频次为0,将遇到的数字选为candidate; 如果Map的容量已满k-1且所有candidate的频次不为零则所有candidate的频次--。

 

References:

[1]https://www.zhihu.com/question/49973163

 

找到数组中频次大于1/k的数

原文:https://www.cnblogs.com/fakedestiny/p/10996980.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!