九度OJ 1534 数组中第K小的数目字
九度OJ 1534 数组中第K小的数字
题目1534:数组中第K小的数字
真心的,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-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 ****************************************************************/