首页 > 代码库 > 九度OJ 1534 数组中第K小的数字
九度OJ 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小的数字。
- 输入:
输入可能包含多个测试案例。
对于每个测试案例,输入的第一行为三个整数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面试题
#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-1到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\n", findKth(k)); } return 0; } /************************************************************** Problem: 1534 User: kirchhoff Language: C Result: Accepted Time:960 ms Memory:3256 kb ****************************************************************/
九度OJ 1534 数组中第K小的数字
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。