主题:[讨论]第39次编程比赛结果
liyanguestc_1f:
没有按要求编写函数:若存在这样的i(m个),函数Majority返回m,否则函数返回0。而你返回的是这个自然数 i。
tenm_7f:
方法比较直接,而且没有按要求编写函数:没有完整的计算可能存在的超过半数i的个数
batmanlf_10f:
=>Wrong,right is 6,but you get 0
array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
wlsss_15f:
=>Wrong,right is 6,but you get 4
array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
joekings_f17:
你和 1楼的liyanguestc一样没有按要求编写函数。你们算法大体上也是一致的,
排序后,你查找的方法有问题,参见完整代码。
ghbxx2004_f20:
没有按要求编写函数:题目已知 m > n/2,
而你的代码是 :if(m >= (n/2) ){return m;}
bloodybg_f21:(修改后,对你的程序进行了效率测试)
使用全局变量arrayNum时,
int Majority(int vote[], int n)
{
//arrayNum = 0;//在调用函数Majority时arrayNum没有赋值为0
int *a, *b;
...
//结果造成你的函数不能循环使用,
//原因是,在第二次调用函数Majority时,arrayNum的值不是0,而继续保存上一次的遗留值。
gohan_f28:
=>Wrong,right is 6,but you get 0
array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
hwjian_f31:
=>Wrong,right is 6,but you get 10
array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
天边蓝_f32:
你和 1楼的liyanguestc一样没有按要求编写函数。你们算法大体上也是一致的,
排序后,你查找的方法有点繁琐,参见完整代码。
forjane_f42:
=>Wrong,right is 6,but you get 0
array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
wksuper_f47:
没有按要求编写函数:没有计算可能存在的超过半数i的个数。
yelv_f49:
方法比较直接,而且没有按要求编写函数:没有没有完整的计算可能存在的超过半数i的个数。
大部分未通过测试的朋友,主要原因是没有按要求编写函数接口,或者写代码时过于疏忽,
因为上面的朋友使用的都是同一种算法:先排序,后查找并计数。
有完整的代码供大家参考,如下:(n=1千万时,耗时781 ms)
int Compare(const void*x, const void *y){
return *(int*)x - *(int*)y;
}
int Majority (int vote[], int n)
{
int i,j,half = n/2;
int count = half+1;
qsort(vote, n, sizeof(int), Compare);//排序
//sort(vote,vote+n);
for(i = 0; i < int(n/2.0+0.5); i++){//平台式查找
if(vote[i] == vote[i + half]){
for(j = i + half + 1; j < n; j++){
if(vote[j] == vote[i])
++count;//开始记数
else
break;
}
return count;//计算完毕,结束函数
}
}
return 0;
}
效率测试:
当数组的大小为2万时,一些朋友的程序开始见慢,
wlsss_4f:time cost is :3375 ms
hyl084_f25:time cost is :5594 ms
qingfengjianke_f46:time cost is :1640 ms
jihao111_f53:time cost is :3329 ms
而其他朋友的程序都能控制在 10ms(左右)以下。
当数组的大小为1千万时
jackin0627_3f: 938 ms
01835cwj_6f: 2766 ms
rickone_f18: 313 ms
bloodybg_f21: 688 ms
孤独的猫_f22: 531 ms
天国龙_f23: 516 ms
jxstudying_f24:1141 ms
xyhx_f26: 860 ms
火海时代_f27: 1375 ms
SonicLing_f30: 8328 ms
neverPE_35: 0 ms
yunzhou008_f37:5000 ms
amen_f41: 4078 ms
wshong_f44: 1500 ms
侍鱼_f48: 515 ms
liangbch: 172 ms
BigCarrot: 232 ms
[color=008000]当数组的大小为1亿(机器状态最好时)时
neverPE_35: 0 ms //为什么总是0,是不是编译器有问题!
liangbch: 1703 ms
BigCarrot: 2329 ms
题目标准算法: 830 ms[/color]
我宣布次数比赛的冠军是 [color=800000]neverPE 兄[/color],请neverPE 准备第40次编程比赛。
[color=000080]赠送题回复得人不多,且都使用了相似得算法,题目的标准算法也和大家的几乎一样。[/color]
P.S.测了一天了,几乎要崩溃了!如果测试结果有令大家不满意的地方,请多多见谅!

您所在位置:





