Posted on 2007-10-07 16:06
ZelluX 阅读(546)
评论(0) 编辑 收藏 所属分类:
Algorithm
Problem: You are given n real numbers - they are NOT sorted. Develop a linear time（O(n)）algorithm to find the largest gap between consecutive numbers when the n numbers are sorted. For example, given:
10 23 7 1 35 27 50 41
the algorithm should produce 13 as its result, since the sorted list is:
1 7 10 23 27 35 41 50
and the largest gap is 13 (between 10 and 23).
Please note that your algorithm cannot actually sort the n numbers.
Macsy (真心) 于 (Fri Oct 5 11:59:16 2007) 提到:
有一个方法需要额外的O(n)的空间。
首先找到最大最小数max,min
max gap 肯定不小于 (max-min)/n 。
然后以(max-min)/n为步长，建立n个桶
每个桶里面记录落在这个桶中的最大最小值。
最后顺序扫描这n个桶中的值就可以了。
大概代码是
input: a[n];
min=min_of(a[1..n]);
max=max_of(a[1..n]);
step=(max-min)/n;
b[0..n].min=maxfloat; b[0..n].max=-maxfloat;
for i=1 to n
ind = (a[i]-min)/step;
b[ind].min=min(b[ind].min, a[i]);
b[ind].max=max(b[ind].max, a[i]);
maxgap=step;
last=b[0].max;
for i=1 to n
if (b[i].min != maxfloat)
maxgap=max(maxgap, b[i].min-last);
last=b[i].max;
output maxgap