找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

[ 海量数据处理 ] 【守望者 海量数据】最大间隙问题

2014-09-24 12:10| 发布者: zhouy | 查看: 506 | 收藏

摘要: 给定n个实数,求着n个实数在实轴上向量2个数之间的最大差值,要求线性的时间算法。
给定n个实数,求着n个实数在实轴上向量2个数之间的最大差值,要求线性的时间算法。

你有新的观点?  

已有1参与讨论

  • 思路:

    方案1:最先想到的方法就是先对这n个数据进行排序,然后一遍扫描即可确定相邻的最大间隙。但该方法不能满足线性时间的要求。故采取如下方法:

    s> 找到n个数据中最大和最小数据max和min。

    s> 用n-2个点等分区间[min,max],即将[min, max]等分为n-1个区间(前闭后开区间),将这些区间看作桶,编号为1,2,...,n-2,n-1,且桶 i 的上界和桶i+1的下届相同,即每个桶的大小相同。每个桶的大小为:dblAvrGap=(max-min)/(n-1)。实际上,这些桶的边界构成了一个等差数列(首项为min,公差为d=dblAvrgap),且认为将min放入第一个桶,将max放入第n-1个桶。

    s> 将n个数放入n-1个桶中:将每个元素x分配到某个桶(编号为index),其中 index= (x-min)/dblAvrGap 的下限 + 1 ,并求出分到每个桶的最大最小数据。

    s> 最大间隙:除最大最小数据max和min以外的n-2个数据放入n-1个桶中,由抽屉原理可知至少有一个桶是空的,又因为每个桶的大小相同,所以最大间隙不会在同一桶中出现,一定是某个桶的上界和某个桶的下界之间隙,且该两桶之间的桶一定是空桶。也就是说,最大间隙在桶i的上界和桶j的下界之间产生 j>=(i+1)。一遍扫描即可完成。

    参考c源码:

    #include <iostream>  
    #include <vector>  
    using namespace std;  
      
    struct  Bucket{  
        double min;  
        double max;  
        int flag;  
    };  
    //桶排序,计算最大间隙  
    double MaxGap( double *arr, int len){  
        if( len<0 ) return 0;  
        double max=arr[0],min=arr[0];  
        for( int i=0; i<len; i++){             //找最大最小值  
            if( arr>max) max=arr;  
            if( arr<min) min=arr;  
        }  
      
        vector<Bucket> bucket(len-1);  
        for( int i=0; i<len-1; i++){           //初始化桶  
                bucket.max= min+i*(max-min)/(len-1);  
                bucket.min= min+(i+1)*(max-min)/(len-1);  
                bucket.flag=0;  
        }  
      
        double gap=(max-min)/(len-1);  
        for( int i=0; i<len; i++){            //分入桶中  
            int index=(int)((arr-min)/gap);  
            if( index>=len-1) index = len-2;  
            if( bucket[index].flag==0 ){  
                bucket[index].max=arr;  
                bucket[index].min=arr;  
            }  
            if( bucket[index].max<arr )  
                bucket[index].max=arr;  
            if( bucket[index].min>arr)  
                bucket[index].min=arr;  
            bucket[index].flag=1;  
        }  
      
        double maxgap=0;  
        double low=bucket[0].max;  
        for( int i=0; i<len-1; i++){           //找最大间隙  
            while( bucket.flag==0 ) i++;  
            if( i<len-1){  
            double t = bucket.min-low;  
            maxgap = t>maxgap?t:maxgap;  
            low=bucket.max;  
            }  
        }  
      
        return maxgap;  
    }  
    int main()  
    {  
        double arr[] = {-31,-41,4,-3,4,-1,-97,-93,-23,-84};  
        cout<<"MAX:"<<MaxGap(arr, sizeof(arr)/sizeof(double));  
        return 0;  
    }
    zhouy

    2014-10-17 14:33

赞过此文的人

推荐阅读

[守望者 内推职位]中电科网络信息安全有限责任公司
[守望者 内推职位]中电科网络信息安全
中国电子科技集团公司第三十研究所(以下简称:三十所)创建于1965年,是集通
[猎头职位] 英国金融公司 liquid(利源软件)Linux C++高级开发
[猎头职位] 英国金融公司 liquid(利源
Liquid Capital Group 是一家总部位于伦敦的专门从事金融衍生品交易和做市业
【守望者 内推职位】腾讯平台架构后台开发工程师
【守望者 内推职位】腾讯平台架构后台
守望者:腾讯后端开发,职位在深圳,年薪30~35W,成都主要为游戏开发相关职位
[守望者 猎头职位] 某民机航电公司  研发技术副总监 VxWorks软件高级工程师 Linux软件 ...
[守望者 猎头职位] 某民机航电公司 研
以下职位为猎头职位。有兴趣可将简历发送到362528717@qq.com或者加QQ交流,匹
[猎头职位] 加拿大 宏利金融  .Net 高级开发
[猎头职位] 加拿大 宏利金融 .Net 高
守望者:本职位为金融开发相关陪伴,要求有较强的架构设计能力,开发能力,分
[猎头职位] 高级嵌入式系统架构师
[猎头职位] 高级嵌入式系统架构师
高级嵌入式系统架构师
[内部推荐]重庆金鑫智慧java高级程序员
[内部推荐]重庆金鑫智慧java高级程序员
守望者:重庆金鑫智慧是重庆南桐矿业集团公司旗下的子公司,有专业的队伍进行
【猎头职位】欧美软件开发公司  ASP.NET高级工程师
【猎头职位】欧美软件开发公司 ASP.NE
公司专门对欧美软件外包服务提供商。公司在多个领域有着独到和突出的技术,包
[猎头职位] 系统测试__安全产品测试
[猎头职位] 系统测试__安全产品测试
系统测试__安全产品测试
[猎头职位] windows客户端开发工程师或leader 公共技术客户端高级架构师(深圳) ... .. ...
[猎头职位] windows客户端开发工程师或
守望者:以下两个职位为互动娱乐高端管理职位。主要工作为游戏开发及项目管理
【守望者  面试交流】HR谈 如何使用E-mail投递简历
【守望者 面试交流】HR谈 如何使用E-m
守望者:现在的简历一般都使用E-mail发送,然而,随着信息泛滥,HR需要从浩瀚

推荐阅读

[守望者 内推职位]中电科网络信息安全有限责任公司
[守望者 内推职位]中电科网络信息安全
中国电子科技集团公司第三十研究所(以下简称:三十所)创建于1965年,是集通
[猎头职位] 英国金融公司 liquid(利源软件)Linux C++高级开发
[猎头职位] 英国金融公司 liquid(利源
Liquid Capital Group 是一家总部位于伦敦的专门从事金融衍生品交易和做市业
【守望者 内推职位】腾讯平台架构后台开发工程师
【守望者 内推职位】腾讯平台架构后台
守望者:腾讯后端开发,职位在深圳,年薪30~35W,成都主要为游戏开发相关职位
[守望者 猎头职位] 某民机航电公司  研发技术副总监 VxWorks软件高级工程师 Linux软件 ...
[守望者 猎头职位] 某民机航电公司 研
以下职位为猎头职位。有兴趣可将简历发送到362528717@qq.com或者加QQ交流,匹
[猎头职位] 加拿大 宏利金融  .Net 高级开发
[猎头职位] 加拿大 宏利金融 .Net 高
守望者:本职位为金融开发相关陪伴,要求有较强的架构设计能力,开发能力,分
[猎头职位] 高级嵌入式系统架构师
[猎头职位] 高级嵌入式系统架构师
高级嵌入式系统架构师
[内部推荐]重庆金鑫智慧java高级程序员
[内部推荐]重庆金鑫智慧java高级程序员
守望者:重庆金鑫智慧是重庆南桐矿业集团公司旗下的子公司,有专业的队伍进行
【猎头职位】欧美软件开发公司  ASP.NET高级工程师
【猎头职位】欧美软件开发公司 ASP.NE
公司专门对欧美软件外包服务提供商。公司在多个领域有着独到和突出的技术,包
[猎头职位] 系统测试__安全产品测试
[猎头职位] 系统测试__安全产品测试
系统测试__安全产品测试
[猎头职位] windows客户端开发工程师或leader 公共技术客户端高级架构师(深圳) ... .. ...
[猎头职位] windows客户端开发工程师或
守望者:以下两个职位为互动娱乐高端管理职位。主要工作为游戏开发及项目管理
【守望者  面试交流】HR谈 如何使用E-mail投递简历
【守望者 面试交流】HR谈 如何使用E-m
守望者:现在的简历一般都使用E-mail发送,然而,随着信息泛滥,HR需要从浩瀚