Posted on 2007-10-07 16:06
ZelluX 閱讀(566)
評論(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