give two sorted array, find the k-th smallest element of union of A and B(二)
nd B is not differed in an extreme way; ie, all elements in A are smaller than B). If you are wondering, yes, you could choosei to be A’s middle. In theory, you could choose any values for i and j as long as the invariant i+j = k-1 is satisfied.
here is the code:
[cpp]
#include
#include
using namespace std;
int flag = 0;
int get_k_th_minimum(int *a, int m, int *b, int n, int k) {
assert(m >= 0);
assert(n >= 0);
assert(k <= (m + n));
int i = (int)((double)m / (m + n) * (k + 1));
int j = (k - 1) - i;
assert(i >= 0);
assert(j >= 0);
assert(i <= m);
assert(j <= n);
int Ai_1 = ((i == 0) INT_MIN : a[i-1]);
int Bj_1 = ((j == 0) INT_MIN : b[j-1]);
int Ai = ((i == m) INT_MAX : a[i]);
int Bj = ((j == n) INT_MAX : b[j]);
if(Bj_1 < Ai && Ai < Bj) {
flag = 0;
return Ai;
} else if(Ai_1 < Bj && Bj < Ai) {
flag = 1;
return Bj;
}
assert((Ai > Bj && Ai_1 > Bj) || (Ai < Bj && Ai < Bj_1));
if(Ai < Bj) {
get_k_th_minimum(a + i + 1, m - i - 1, b, j, k - i - 1);
} else {
get_k_th_minimum(a, i, b + j + 1, n - j - 1, k - j - 1);
}
}
void main() {
int i = 0;
int j = 0;
int a[] = {1, 3, 5, 7, 9};
int b[] = {2, 4, 6, 8, 10};
int len_a = sizeof(a) / sizeof(int);
int len_b = sizeof(b) / sizeof(int);
int k = 6;
int result = get_k_th_minimum(a, len_a - 1, b, len_b - 1, k);
if(flag == 0) {
while(a[i] != result) {
cout << a[i] << " ";
i++;
}
for(j = 0; j < k - i - 1; j++) {
cout << b[j] << " ";
} www.2cto.com
cout << result << endl;
} else {
while(b[i] != result) {
cout << b[i] << " ";
i++;
}
for(j = 0; j < k - i - 1; j++) {
cout << a[j] << " ";
}
cout << result << endl;
}
getchar();
}