Это тот же вопрос, что и Алгоритм поиска n-го по величине числа в двух массивах размера n, ЗА ИСКЛЮЧЕНИЕМ того, что два отсортированных массива имеют разные размеры.
Я попытался реализовать вариант алгоритма, аналогичный предложенному для решения моей задачи, но не могу показать его правильность. Похоже, что для k = 6 он не работает. Возвращаемая пара — это индексы для list1 и list2 соответственно, когда алгоритм завершает работу.
#include <iostream>
#include <utility>
using namespace std;
pair<int, int> smallestKElements(int list1[], int list2[], int k) {
// TODO: pass in the array sizes as parameters
int m = 8;
int n = 5;
// initialize array pointers such that i + j = k
int i = m/2;
int j = n/2;
if (i + j + 2 < k) {
while (i + j + 2 != k) {
if (++i + j + 2 == k)
break;
if (i + ++j + 2 == k)
break;
}
} else if (i + j + 2 > k) {
while (i + j + 2 != k) {
if (--i + j + 2 == k)
break;
if (i + --j + 2 == k)
break;
}
}
// step forward in one array and step backward in another array
// decrement step size with every iteration until it is 0
int s = k/2;
while (s > 0) {
if (list1[i] < list2[j]) {
if (m - 1 - i >= s &&
j >= s) {
i += s;
j -= s;
}
} else {
if (i >= s &&
n - 1 - j >= s) {
i -= s;
j += s;
}
}
s = s/2;
}
pair<int, int> r(i,j);
return r;
}
int main() {
int list1[] = {1, 4, 6, 7, 10, 11, 13, 27};
int list2[] = {2, 3, 20, 40, 60};
pair<int, int> test = smallestKElements(list1, list2, 6);
cout << test.first << "," << test.second << endl;
return 0;
}
vector<int>
вместо массива в стиле C. - person M.M   schedule 23.05.2014