[PAT解题报告] Median
两个有序数组的中位数是个经典的问题,但是本题对时间要求不高,所以可以用归并排序的方法来做,所以就很简单了。归并排序找到第k个元素就可以了。时间复杂度是O(k)其中k是(na + nb)  / 2。还有题目里说的long,我还是用了long long。
代码:

#include <cstdio>
#include <string>
#include <cstring>
using namespace std;

long long a[1000006], b[1000006];

int main() {
int na,nb;
    scanf("%d",&na);
    for (int i = 0; i < na; ++i) {
        scanf("%lld",a + i);
    }
    scanf("%d", &nb);
    for (int j = 0; j < nb; ++j) {
        scanf("%lld", b + j);
    }
    for (int i = 0, j = 0, k = 0, c = 0,want = (na + nb - 1) >> 1; (i < na) || (j < nb); ++k) {
        if (i >= na) {
            c = 1;
        }
        else if (j >= nb) {
            c = 0;
        }
        else {
            c = (a[i] < b[j])?0:1;
        }
        if (c == 0) {
            if (k == want) {
                printf("%lld\n",a[i]);
                break;
            }
            ++i;
        }
        else {
            if (k == want) {
                printf("%lld\n",b[j]);
                break;    
            }
            ++j;
        }
    }
    return 0;
}
原题链接: http://www.patest.cn/contests/pat-a-practise/1029

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 16:33
重庆工商大学_2024
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议