`
cynhafa
  • 浏览: 153131 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

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

 
阅读更多

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

答案1:
创建一个hash_map,key为数组中的数,value为此数出现的次数。遍历一遍数组,用hash_map统计每个数出现的次数,并用两个值存储目前出现次数最多的数和对应出现的次数。
这样可以做到O(n)的时间复杂度和O(n)的空间复杂度,满足题目的要求。
但是没有利用“一个数出现的次数超过了一半”这个特点。也许算法还有提高的空间。

答案2:
使用两个变量A和B,其中A存储某个数组中的数,B用来计数。开始时将B初始化为0。
遍历数组,如果B=0,则令A等于当前数,令B等于1;如果当前数与A相同,则B=B+1;如果当前数与A不同,则令B=B-1。遍历结束时,A中的数就是要找的数。
这个算法的时间复杂度是O(n),空间复杂度为O(1)。
这道题也可以这么解,先两两比较,如果相同则留下,如果不同则两个都删除,则一遍之后,那个多于一半的数在剩下的里面还是多于一半,然后再重复上述过程,直到最后
由于出现过半,所求数肯定是出现次数最多的数,即转化为“求出现次数最多的数”,利用hashmap, O(N)时间内可以求得。
int max;
int dat;
Hashmap map;
for each num
if(map.has(num)) {
int cnt = map.get(num);
map.set(num, cnt+1);
if(cnt + 1 > max) { max = cnt+1; dat = num; }
}
else map.put(num, 1);
//for each

>the data you want is dat that appears max times.
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics