主题：第41次编程比赛之口水题
BigCarrot [专家分：10] 发布于 2006-09-14 21:57:00
这个题目是半年前一个朋友去google面试时被问的一个题目, 我觉得与第39次比赛的第一题比较相似,所以称之为口水题
求一个自然数数组中最中间的那个数, 如果数组元素个数为偶数个,则求出从大到小第 n/2 个, 函数原型为
unsigned int Mid(unsigned int array[], unsigned int n);
例1
n = 5; array = {6, 7, 8, 9, 10};
结果应该是8
例2
n = 4; array = {2, 2, 3, 3};
结果应该是3
测试环境
P3M 1.2G 640MB
visual studio 2002, release mode
运行时间为10s, 数组长度最长为100M, 再大我的内存就不够了
本次比赛截止时间为星期六下午一点整，到时间后我会另开一贴供大家提交自己的测试数据, 到星期天晚上七点截止. 这些数据和我自己的数据都会被用来测试大家提交的程序.
回复列表 （共7个回复）
沙发
BigCarrot [专家分：10] 发布于 2006-09-14 21:58:00
test
板凳
格子裙 [专家分：15760] 发布于 2006-09-14 22:06:00
[quote]
则求出从大到小第 n/2 个
[/quote]
[quote]
例2
n = 4; array = {2, 2, 3, 3};
结果应该是3
[/quote]
----------------------
从大到小第 n/2 个, array = {2, 2, 3, 3};
n = 4;
n/2 = 2;
从大到小第2个数,如果相同的只算一个数,那么是2 如果相同的数不只算一个数,则是3
请楼主清楚的说明.
3 楼
joekings [专家分：550] 发布于 2006-09-15 09:07:00
#include <stdio.h>
#include <stdlib.h>
int compare( const void *arg1, const void *arg2 );
unsigned int Mid(unsigned int array[], unsigned int n)
{
int i;
qsort((void*)array,n,sizeof(unsigned int),compare);
i=n/2;
return array[i];
}
int compare( const void *arg1, const void *arg2 )
{
int *p1=(int*)arg1;
int *p2=(int*)arg2;
if(*p1>*p2)
return 1;
if(*p1<*p2)
return -1;
return 0;
}
4 楼
braveheart2001 [专家分：30] 发布于 2006-09-15 11:03:00
unsigned int Mid(unsigned int array[],unsigned int n)
{
unsigned int N,i,j;
N=n-1;
for(i=0;i<n;++i)
{
for(j=0;j<N;++j)
{
Camp(array[j],array[j+1]);
}
N-=1;
}
if(n%2==0)return array[n/2-1];
if(n%2==1)return array[n/2];
}
void Camp(unsigned int& a,unsigned int& b)
{
unsigned int temp;
if(a<b)
{
temp=a;
a=b;
b=temp;
}
}
5 楼
WinWing [专家分：3450] 发布于 2006-09-16 04:09:00
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int sort_func( const void *a, const void *b)
{
if(*(unsigned int*)a>*(unsigned int*)b)
return 1;
else if(*(unsigned int*)a<*(unsigned int*)b)
return -1;
else
return 0;
}
unsigned int Mid(unsigned int array[], unsigned int n)
{
qsort((void*)array,n,sizeof(unsigned int),sort_func);
return n%2?array[(n-1)/2]:array[n/2];
}
6 楼
ITER [专家分：680] 发布于 2006-09-16 10:47:00
#include <iostream>
using namespace std;
int cmp(const void *p1,const void *p2)
{
unsigned int a=*(const int *)p1;
unsigned int b=*(const int *)p2;
if(a>b)
return -1;
else return 1;
}
unsigned int Mid(unsigned int array[], unsigned int n)
{
if(1==n%2) //引用题目“求一个自然数数组中最中间的那个数”
return array[n/2]; //返回数组中间那个数
/*引用题目“如果数组元素个数为偶数个,则求出从大到小第 n/2 个”*/
else qsort(array,n,sizeof(int),*cmp); //按从大到小排序
return array[n/2-1]; //返回第n/2大的那个数
}
main()
{
unsigned int arr[]={1,2,3,4,5,6};
cout<<Mid(arr,6);
}
7 楼
sllone [专家分：150] 发布于 2006-09-16 12:27:00
已删!
我来回复
您所在位置：