Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

求相邻数最大间隔

Posted on 2007-10-07 16:06 ZelluX 阅读(403) 评论(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


只有注册用户登录后才能发表评论。


网站导航: