最大间隙问题

最大间隙问题

时间: 1ms        内存:64M

描述:

最大间隙问题:给定n个实数x1,x2,……,xn,求这n 个数在实轴上相邻2 个数之间的最大差值。假设对任何实数的下取整方法耗时O(1),设计解最大间隙问题的线性时间算法。对于给定的n 个实数x1,x2,……,xn,计算它们的最大间隙。

输入:

输入数据的第1行有1个正整数n,n≤200000。接下来的1行中有n个实数x1,x2,……,xn

输出:

将找到的最大间隙输出.

示例输入:

5
2.3 3.1 7.5 1.5 6.3

示例输出:

3.2

提示:

参考答案(内存最优[3132]):

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;
int main()
{
    int n;
    double maxnum=0;
    cin >> n;
    double data[200000]={0};
    for(int i=0;i<n;i++)
    {
        cin >> data[i];
    }
    sort(data,data+n);
    for(int i=0;i<n-1;i++)
    {
        double x = (data[i+1]-data[i]);
        if(x<0)
            x = -x;
        if(x>maxnum)
            maxnum = x;
    }
    printf("%g\n",maxnum);
    return 0;
}

参考答案(时间最优[104]):

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
double a[2000005],maxx;
int main()
{
    long int n;
    scanf("%ld",&n);
    for(int i=0;i<n;i++)scanf("%lf",a+i);
    sort(a,a+n);
    for(int i=1;i<n;i++)
    {
        maxx=a[i]-a[i-1]>maxx?a[i]-a[i-1]:maxx;
    }
    printf("%g\n",maxx);
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注