百度笔试题请教！

rayeaster 2010-10-15 03:15:30

有一个无序的实数序列x1,x2.....xn，请设计个算法在线性时间内找到相邻（不是序列相邻，而是在实数轴上相邻）两点间最大距离？？

感觉没有排序的话，怎么知道哪两点是相邻的呢？

...全文

252 8 打赏收藏转发到动态举报

写回复

用AI写文章

8 条回复

切换为时间正序

请发表友善的回复…

发表回复

yongganhangxing 2011-10-07

打赏
举报

//最大距离肯定大于平均距离，用桶装数
double max_gap(double* num, int n)
{
int i;
//找出最大最小值
double max=0.0,min = INT_MAX;
for(i=0;i<n;i++)
{
if(num[i]>max) max=num[i];
if(num[i]<min) min=num[i];
}

int *count=new int[n]; //动态分配，实际分到每个桶的数据个数
double *low=new double[n]; //实际分到每个桶的最小数据(下界)
double *high=new double[n]; //实际分到每个桶的最大数据（上界）

for(i = 0; i < n; i++) //初始化每个桶
{
count[i] = 0;
low[i] = max;
high[i] = min;
}

double ave=(max-min)/(n-1);

//按如下规则将num[i]分配到某个桶(编号doublemp)中
for(i=0;i < n; i++)
{
int temp=(int)((num[i]-min)/ave);
count[temp]++;
//调整分到该桶的最大最小数据
if(num[i] > high[temp])
high[temp] = num[i];
if(num[i] < low[temp])
low[temp] = num[i];
}

//寻找最大间隙
double left = high[0], res = 0.0;
for(i = 1;i < n; i++)
{
if(count[i]>0)
{
double temp = low[i]- left;
if(temp > res) res = temp;
left = high[i];
}
}
return res;
}

int main()
{
int num;
cin >> num;
double* pdArr = new double[num];
for (int i = 0; i < num; i++)
{
cin >> pdArr[i];
}
cout << max_gap(pdArr, num)<<endl;
return 0;
}

rayeaster 2010-10-15

打赏
举报

[Quote=引用 6 楼 shayla 的回复:]
关键在于:距离平均值为（max-min）/n-1, 则距离最大的数必然大于这个值这句话

假设有4个数,最小为0.2, 最大为0.8.
那么这四个数的平均距离为(0.8-0.2)/3 = 0.2
则必然存在两个数的差大于等于0.2,即距离最大的两个数必然不会小于0.2.

分成三个桶,分别是0.2~0.4, 0.4~0.6, 0.6~0.8.
那么距离最大的两个数必然不在同一个桶内……
[/Quote]
谢谢！明白了！
第一遍遍历，得到最大值最小值！
第二遍遍历，算出平均距离，分成n-1个桶，把每个数按照其与最小值的距离分别入桶
第三遍遍历桶，找出最终距离最大值~

shayla 2010-10-15

打赏
举报

关键在于:距离平均值为（max-min）/n-1, 则距离最大的数必然大于这个值这句话

假设有4个数,最小为0.2, 最大为0.8.
那么这四个数的平均距离为(0.8-0.2)/3 = 0.2
则必然存在两个数的差大于等于0.2,即距离最大的两个数必然不会小于0.2.

分成三个桶,分别是0.2~0.4, 0.4~0.6, 0.6~0.8.
那么距离最大的两个数必然不在同一个桶内.
依次比较上一个桶的最大值与下一个桶的最小值的差值,找最大的即可.

rayeaster 2010-10-15