Lintcode48 Majority Number III solution 题解

【题目描述】

Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array.Find it.

Notice:There is only one majority number in the array.

给定一个整型数组,找到主元素,它在数组中的出现次数严格大于数组元素个数的1/k。

注意:数组中只有唯一的主元素

【题目链接】

http://www.lintcode.com/en/problem/majority-number-iii/

【题目解析】

依然抵消法,但是为了更快的获取,消除,增加次数,这里应该用hashtable(dictionary in python)

然后在剩下的数中找到出现次数最多的数,就是majority number(因为前提是只有一个majority number)

如果不确定,可以再loop一次找出这个数的出现次数

【参考答案】

http://www.jiuzhang.com/solutions/majority-number-iii/

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,959评论 0 23
  • 小时候,幸福是件简单的事,长大后,简单是很幸福的事。 小时候,我的幸福就是雨后在小石子路捡漂亮的小石头,爬山上最大...
    葶瞸阅读 262评论 0 0
  • 宁夏天元锰业集团,视环保为生命,依靠自主创新,自加压力,实现清洁生产、循环发展,已成为全球金属锰行业环保标杆。近日...
    4887193eb594阅读 295评论 0 0
  • “你来了?” “我来了” “嗯.” “嗯 好” 你敲响了我房间的门,我抬头见你还是穿的那一件灰色大衣。门外的天...
    何筱一阅读 872评论 0 2