九度OJ 1534 數(shù)組中第K小的數(shù)字
來(lái)源：程序員人生 發(fā)布時(shí)間：2015-01-09 08:12:06 閱讀次數(shù)：2826次
題目1534：數(shù)組中第K小的數(shù)字
時(shí)間限制：2 秒
內(nèi)存限制：128 兆
特殊判題：否
提交：1524
解決：307
-
題目描寫(xiě)：
-
給定兩個(gè)整型數(shù)組A和B。我們將A和B中的元素兩兩相加可以得到數(shù)組C。
比方A為[1,2]，B為[3,4].那末由A和B中的元素兩兩相加得到的數(shù)組C為[4,5,5,6]。
現(xiàn)在給你數(shù)組A和B，求由A和B兩兩相加得到的數(shù)組C中，第K小的數(shù)字。
-
輸入：
-
輸入可能包括多個(gè)測(cè)試案例。
對(duì)每一個(gè)測(cè)試案例，輸入的第1行動(dòng)3個(gè)整數(shù)m，n， k(1<=m,n<=100000， 1<= k <= n *m)：n，m代表將要輸入數(shù)組A和B的長(zhǎng)度。
緊接著兩行， 分別有m和n個(gè)數(shù)， 代表數(shù)組A和B中的元素。數(shù)組元素范圍為[0,1e9]。
-
輸出：
-
對(duì)應(yīng)每一個(gè)測(cè)試案例，
輸出由A和B中元素兩兩相加得到的數(shù)組c中第K小的數(shù)字。
-
樣例輸入：
-
2 2 3
1 2
3 4
3 3 4
1 2 7
3 4 5
-
樣例輸出：
-
5
6
-
來(lái)源：
- 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){//這個(gè)雖然和cal2 有相同的輸出，可是做了很多的無(wú)用計(jì)算，會(huì)超時(shí)
long long i, j;
long long cnt = 0;
j=0;
for(i=0;i<m;++i)
{
j=0;//每次都要初始化為0，重新開(kāi)始計(jì)數(shù)
while(j<n&&A[i]+B[j]<=mid)
++j;
cnt+=j;
}
return cnt;
}
long long cal2 (long long mid){
/*本函數(shù)能夠節(jié)省沒(méi)必要要的計(jì)算值，A從小到大遍歷，B從大到小遍歷便可，
假設(shè)A[i]+B[j]<=mid了，那末此時(shí)的j對(duì)i+1來(lái)說(shuō)，范圍還是有些大了，繼續(xù)遞減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);//無(wú)用計(jì)算太多，會(huì)超時(shí)
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
****************************************************************/
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
