找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

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

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

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

推荐阅读

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

行业聚焦  面试交流  职位推荐  开发视频   技术交流  腾讯微博  新浪微博

友情链接:课课家教育  阿里云  鲜果  W3Cfuns前端网  中国企业家  环球企业家  投资界  传媒梦工场  MSN中文网  Android开发者社区  cnbeta  投资中国网  又拍云存储  美通说传播  IT茶馆  网商在线  商业评论网  TechOrange  IT时代周刊  3W创新传媒  开源中国社区  二维工坊  Iconfans  推酷  智能电视网  FreeBuf黑客与极客  财经网  DoNews  凤凰财经  新财富  eoe移动开发者社区  i黑马  网易科技  新浪科技  搜狐IT  创业家  创业邦  腾讯财经  福布斯中文网  天下网商  TechWeb  雷锋网  新浪创业  和讯科技  品途O2O  极客公园  艾瑞网  抽屉新热榜  卖家网  人民网通信频道  拉勾网  创新派  简单云主机  

手机版|黑名单|守望者在线 在线教育 linux 高级程序设计 C/C++ 大数据 ( 蜀ICP备14029946号

成都守望者科技有限公司 © 2013-2016 All Rights Reserved