• 美团2016 C\C++研发工程师 笔试题

    2015/09/26 王先生 14 评论

给定一个递增序列,a1 <a2 <…<an 。定义这个序列的最大间隔为d=max{ai+1 – ai }(1≤i<n),现在要从a2 ,a3 ..an-1 中删除一个元素。问剩余序列的最大间隔最小是多少?

输入描述:
第一行,一个正整数n(1<=n<=100),序列长度;接下来n个小于1000的正整数,表示一个递增序列。

输出描述:
输出答案。

输入例子:
5
1 2 3 7 8

输出例子:
4

2 1 收藏


直接登录
最新评论
  • 王先生 学生 2015/09/27

    动态规划来解好像挺好

  • Delostik 学生 2015/09/27

    最大值最小问题一般二分答案就能做……

    二分ans,然后O(n)判定,总复杂度O(nlgn)

    • Delostik 学生 2015/09/27

      突然感觉判定有点问题……
      我是这么想的,对于第i个数,第i+1个数有俩选择(删除或保留),判定的时候加一个计数器,为了维持这个ans是正确的只能删一个数……应该可以做到O(n)

      • 王先生 学生 2015/09/27

        能给具体的代码么

        • Delostik 学生 2015/09/27

          #include
          using namespace std;

          int n;
          int a[1004];
          int l = 1001, r = 0;

          bool check(int res) {
          int cnt = 0;
          for (int i = 0; i res) {
          if (a[i+2] – a[i] > n;
          for (int i = 1; i > a[i];
          r = max(r, a[i]);
          l = min(l, a[i]);
          }
          a[0] = a[2];
          a[n+1] = a[n-1];
          while (l > 1;
          if (check(mid)) r = mid;
          else l = mid + 1;
          }
          cout << l << endl;

          }

          不确定这个代码对不对,但是思路想了想应该没什么问题……
          这么小数据暴力也很快的。。

  • 宵伯特 程序员 2015/09/27

    1.先找出当前数列的所有间隔~ O(n)
    2.找到当前数列中的最大间隔~ O(n)
    3.当任意两相邻间隔的和小于当前最大间隔时,则第二步的最大间隔为最小值 ~ O(n)
    4.否则 则为相邻间隔和中的最小值~O(n)

    第一步和第二步可以同时进行
    第三步和第四步可以同时进行

    • 赞,
      还可以优化一下:
      1.找原数列最大间隔M
      2.找A[i]-A[i+2](相当于删除A[i+1])最大间隔N(过程中有小于M的值即可return,否则返回N)

  • qiuzeliang   2015/09/28

    因为是一个递增序列,不管删除中间那个元素,都会使原序列相邻元素之间的间隔不变小,即大于等于原先的值,所以只要计算原序列的最大间隔输出即可

  • 各位帮我看一看,应该可行,但是在时间复杂性上还很不满意。

    int GetMinValueofMaxDistance(int n, int* array)
    {
    int* distanceArray = new int[n – 1];
    for(int i = 0; i < n – 1; i++)
    {
    distanceArray[i] = array[i+1] – array[i];
    }

    int nMinValueofMaxDistance = 1000;
    for(int i = 0; i < n – 1; i++)
    {
    int maxDistance = 0;
    for(int j = 0; j < n – 1; j++)
    {
    int distance = distanceArray[i+1] + distanceArray[i];

    if(j == i || j == i + 1)
    {
    if(maxDistance < distance)
    maxDistance = distance;
    }
    else
    {
    if(maxDistance maxDistance)
    nMinValueofMaxDistance = maxDistance;
    }
    return nMinValueofMaxDistance;
    }