最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 九度OJ 1534 数组中第K小的数字

    题目1534:数组中第K小的数字

    时间限制:2 秒

    内存限制:128 兆

    特殊判题:

    提交:1524

    解决:307

    题目描写:

    给定两个整型数组A和B。我们将A和B中的元素两两相加可以得到数组C。
    比方A为[1,2],B为[3,4].那末由A和B中的元素两两相加得到的数组C为[4,5,5,6]。
    现在给你数组A和B,求由A和B两两相加得到的数组C中,第K小的数字。

    输入:

    输入可能包括多个测试案例。
    对每一个测试案例,输入的第1行动3个整数m,n, k(1<=m,n<=100000, 1<= k <= n *m):n,m代表将要输入数组A和B的长度。
    紧接着两行, 分别有m和n个数, 代表数组A和B中的元素。数组元素范围为[0,1e9]。

    输出:

    对应每一个测试案例,
    输出由A和B中元素两两相加得到的数组c中第K小的数字。

    样例输入:
    2 2 3
    1 2
    3 4
    3 3 4
    1 2 7
    3 4 5
    样例输出:
    5
    6
    来源:
    Google面试题

    真心的,google面试题真难,(⊙o⊙)…

    #include <stdio.h>
    #include <stdlib.h>
    long long m, n;
    long long k;
    long long A[100000], B[100000];
    long long i;
    int compare(const void * p, const void * q){
    return *(long long *)p – *(long long *)q;
    }

    long long cal (long long mid){//这个虽然和cal2 有相同的输出,可是做了很多的无用计算,会超时
    long long i, j;
    long long cnt = 0;
    j=0;
    for(i=0;i<m;++i)
    {
    j=0;//每次都要初始化为0,重新开始计数
    while(j<n&&A[i]+B[j]<=mid)
    ++j;
    cnt+=j;
    }
    return cnt;
    }
    long long cal2 (long long mid){
    /*本函数能够节省没必要要的计算值,A从小到大遍历,B从大到小遍历便可,
    假设A[i]+B[j]<=mid了,那末此时的j对i+1来说,范围还是有些大了,继续递减j,便可,那末从始至终,j只需要从n⑴到0便可。
    */
    long long i, j;
    long long cnt = 0;
    j = n – 1;
    for (i=0; i<m; ++i){
    while (j>=0 && A[i]+B[j]>mid)
    –j;
    cnt += (j + 1);
    }
    return cnt;
    }

    long long findKth (long long k){
    long long min = A[0] + B[0];
    long long max = A[m – 1] + B[n – 1];
    long long mid;
    long long ans;

    while (min <= max){
    mid = (max – min)/2 + min;
    long long b=cal2(mid);
    //long long b=cal(mid);//无用计算太多,会超时
    if (k <= b){
    max = mid – 1;
    }
    else
    min = mid + 1;
    }
    return min;
    }

    int main(void){
    while (scanf ("%lld%lld%lld", &m, &n, &k) != EOF){
    for (i=0; i<m; ++i)
    scanf ("%lld", &A[i]);
    for (i=0; i<n; ++i)
    scanf ("%lld", &B[i]);
    qsort (A, m, sizeof(long long), compare);
    qsort (B, n, sizeof(long long), compare);
    printf ("%lld
    ", findKth(k));
    }
    return 0;
    }

    /**************************************************************
    Problem: 1534
    User: kirchhoff
    Language: C
    Result: Accepted
    Time:960 ms
    Memory:3256 kb
    ****************************************************************/

    波比源码 – 精品源码模版分享 | www.bobi11.com
    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
    3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

    波比源码 » 九度OJ 1534 数组中第K小的数字

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级