来源:编程之美2.3
题目:该"水王"发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子(包括回帖)的列表,其中帖子作者的ID也在表中,你能快速找出这个传说中的Tango水王吗?
问题实质:寻找数组中出现的半数以上的数.
思路:如果每次删除两个不同的id,则剩下的水王id依然超过总数的一半,可以不断重复这个过程。
问题扩展:如果有3个id,发贴总数都超过了帖子总数的四个之一,如果快速找到他们。思路都差不多。
/*题目:该"水王"发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子(包括回帖)的列表,
其中帖子作者的ID也在表中,你能快速找出这个传说中的Tango水王吗?
问题实质:寻找数组中出现的半数以上的数.
拓展:有3个数,他们的出现次数都超过了总数的1/4.
*/
public class ShuiWang2_3 {
/**
* @param args
*/
public static void main(String[] args) {
int[] id = { 1, 1, 1, 5, 1, 1, 1, 3, 1, 7, 1, 3, 1, 2, 1, 1, 4, 56, 1, 12, 4, 1, 3, 4,
1, 1, 1, 3, 1, 1, 1, 5, 1, 1, 3, 12, 1, 2, 1, 2, 2, 2, 2, 2,2 };
System.out.println(MoreHalfNum(id,id.length));
int id2[] = {5, 5, 5, 7, 7, 8, 8, 8, 8, 2,
2, 2, 2, 2, 2, 2, 2, 5, 5, 5,
6, 5, 6, 7, 7, 7, 7, 7, 7, 7,
7, 5, 7, 2, 2, 2, 5, 5, 5, 8};
printArr(findMore(id2));
}
//每次从数组中删除两个不同的数,不断重复这个过程
//算法中当然不是真的删除数,而是用一个计数器巧妙的实现“删除”
public static int MoreHalfNum(int data[],int n)
{
int candidate=0;//候选值
int nTime=0;//候选值出现的次数
for(int i=0;i<n;i++){
if(nTime==0)//nTime为0时说明需要重新立候选值
{
candidate=data[i];
nTime++;
}else{
if(data[i]==candidate)nTime++;//又出现了,权值加1
else nTime--;//不等,权值减1
}
}
return candidate;
}
public static int[] findMore(int[] data){
int[] res=new int[3];//数组,存出现次数最多的三个数
int[] nTimes={0,0,0};//数组,存每个候选值出现的次数
int i;
for(i=0;i<data.length;i++){
int index;
//1.如果存在某个index,使得nTimes[index]==0,则重新赋候选值
for(index=0;index<3;index++){
if(nTimes[index]==0){
res[index]=data[i];
nTimes[index]++;
break;
}
}
if(index<3)continue;
//2.如果存在index,满足res[index]=id[i]),则对应权值加1
for(index=0;index<3;index++){
if(res[index]==data[i]){
nTimes[index]++;
break;
}
}
if(index<3)continue;
//3.其它情况,对应权值都减1
for(index=0;index<3;index++){
nTimes[index]--;
}
}
return res;
}
private static void printArr(int[] a){
for(int s:a){
System.out.print(s+" ");
}
}
}
分享到:
相关推荐
寻找发帖水王 题目: Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说,Tango有一大“水王”,他不但喜欢发贴,还会回复其他ID发的每个帖子。坊间风闻该“水王”...
向您详细介绍微软测试题,相信您一定会有所收获。
全新特点(详情可以见论坛演示) 全面美化的论坛界面,强大的个人信箱中心; 实用但不豪华的插件,新增的后台管理功能; 1、面版与展区的全面综合:采用功能分类,个性化面版和展区,头部导航分类。...
全面美化的论坛界面,强大的个人信箱中心;实用但不豪华的插件,新增的后台管理功能;论坛管理默认用户名:admin 密码:admin
增加美化: 1.美化了左侧 2.增加每**贴士 3.增加显示IP、浏览器等信息 4.修改签名栏在右侧显示 5.美化的发言的背景,虽然还是有点错误!... 6.... 7.... 8.... 9.... 10.... 11.... 12.... 13.... 14.... 15.... 16.... 17.... 18.... 19.... 20.... 21.... 22....
这是我发布的第一个wap整站程序,以前从没学过asp,很多地方都不足,请大家不要见笑 ^-^ 该程序使用asp语言、access数据库,整合了文章添加、留言本、和评论、自助友链、在线人数统计功能。 你把文件上传到任何...
全面美化的论坛界面,强大的个人信箱中心;实用但不豪华的插件,新增的后台管理功能; 论坛管理默认用户名:admin 密码:admin
现今功能最强的wap论坛,支持表情、ubb,可以查看在线、加好友、发短信,有等级,有头像.
leetcode中国 Contents Chapter 1 游戏之乐 1.1 让CPU占用率曲线听你指挥 CPU占用率曲线为正弦曲线的效果图 ...寻找发帖的“水王” 妙用抵消法 有一个地方存疑:对于N-1个元素,需要多少次遍历才能
这是我发布的第一个wap论坛程序 该程序使用asp语言、access数据库,可以说是现今功能最强的wap论坛,支持表情、ubb,可以查看在线、加好友、发短信,有等级,有头像 conn.asp是数据库连接文件 login.asp...
AngularJS是一门非常值得学习的编程语言,在这系列中,详细地讲述了AngularJS的使用方法!想要学习AngularJS的不妨点击看看吧!
Sublime Text 3绿色汉化破解版下载 编程器完全汉化版。。
Sublime Text 3汉化语言包 Sublime Text 3汉化语言包 Sublime Text 3汉化语言包
鱼c小甲鱼零基础学python全套课后题及答案 鱼c小甲鱼零基础学python全套课后题及答案
内容包括全国各地塑料价格数据表以及预测新建工程的废物回收率模型,这些数据以及文献可以为建模提供思路,文件打开之后要重新解压,以便浏览
要有的算法全部都有,十分有效,比分说层次分析法以及常用的灰色预测,时间序列都有相应的代码和案例,可供毫无基础和经验的同学直接上手建模。