posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

          求相鄰數(shù)最大間隔

          Posted on 2007-10-07 16:06 ZelluX 閱讀(572) 評(píng)論(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)  提到:

          有一個(gè)方法需要額外的O(n)的空間。
          首先找到最大最小數(shù)max,min
          max gap 肯定不小于 (max-min)/n 。
          然后以(max-min)/n為步長,建立n個(gè)桶
          每個(gè)桶里面記錄落在這個(gè)桶中的最大最小值。
          最后順序掃描這n個(gè)桶中的值就可以了。

          大概代碼是
          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

          主站蜘蛛池模板: 原平市| 新宁县| 遂川县| 阳朔县| 清丰县| 吉安县| 武隆县| 洮南市| 会同县| 九龙坡区| 曲阳县| 寻乌县| 漳州市| 桐城市| 海安县| 德庆县| 正阳县| 泰州市| 石泉县| 海丰县| 五大连池市| 新泰市| 昌乐县| 石柱| 西贡区| 东兴市| 南宫市| 鹤壁市| 瓦房店市| 大邑县| 额济纳旗| 遵义县| 溧阳市| 成都市| 三原县| 桃园市| 河北省| 利辛县| 建宁县| 永修县| 泰和县|