PAT甲级1029 Median：[C++题解]贪心、二路归并

文章目录

• • • 题目分析
    • 题目来源

题目分析

来源：acwing

分析:
如果直接排序，时间复杂度是$O(nlogn)，n=2\ast 10^5$会超时，本题不能直接排序做。 其实，这题考察的是归并排序中的归并成有序序列。时间复杂度为O(n).

ac代码

#include<bits/stdc++.h> using namespace std; const int N = 200020;int n, m; int a[N],b[N], c[N*2];int main(){cin >> n;for(int i = 0; i< n; i++) cin >> a[i];cin >> m;for(int i = 0; i< m; i++) cin>> b[i];int k = 0,i = 0, j = 0;while( i < n && j < m){if(a[i] < b[j]) c[k++] = a[i++];else c[k++] = b[j++];}while( i < n) c[k++] = a[i++];while( j < m) c[k++] = b[j++];cout<< c[(m+n -1)/2]<<endl; }

题目来源

PAT甲级1029 Median
https://www.acwing.com/problem/content/1508/

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的PAT甲级1029 Median：[C++题解]贪心、二路归并的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。