首页 > 代码库 > 编程之美----寻找发帖“水王”
编程之美----寻找发帖“水王”
题意：在一堆ID号中，有一个ID出现的次数大于总数的一半，如何快速找出那个ID。
我自己的想法是，如果ID号不是很大，用hash来存储每一个ID号出现的次数，出现一次，hash[ID]++，然后和max值比较，若大，则更新max值，复杂度为o(n)。
书上一个好的解法是：每次删除两个不同的ID(不管是否包含“水王"的ID)，那么在剩下的ID列表中，”水王“ID出现的次数仍然超过总数的一半，递归即可求解。复杂度为o(n)。
1 int find(int ID[], int n) 2 { 3 int candicate,ntimes,i; 4 for(i=ntimes=0;i<n;i++) 5 { 6 if(ntime==0) 7 { 8 candicate=ID[i]; 9 ntimes=1;10 }11 else 12 {13 if(candicate==ID[])14 ntimes++;15 else 16 ntimes--;17 }18 }19 return candicate;20 }
编程之美----寻找发帖“水王”
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。