поиск (n * logn) минимальных элементов из суммы двух массивов

Question

У меня есть некоторая проблема в моей домашней работе, мне дают два массива A, B (они отсортированы) с n элементами каждый, мне нужно найти (n * logn) минимальные элементы (или n, если это возможно)из массива, который состоит из элементов, который является суммой одного элемента из массива A и одного элемента из массива B, total number of elemnts in C will be n^2, - C = {a+b | a belongs to A, b belongs to B}, мне нужно сделать это со сложностью O (n * logn).
Спасибозаранее за любую помощь!

PS Я пытался ее решить, но у меня есть некоторые проблемы.Я знаю, что первый элемент будет a1 + b1, a1 первый элемент из A, b1 первый элемент из B.

edited

Также все элементы в C отличаются.

Answer 1

этот код, приведенный ниже, будет делать то, что использует подсказку, которую вы дали. 2 элемента отсортированы, и его порядок равен числу элементов, которое необходимо найти:

int m = n *lon(n);
a[n] = max_int;
b[n] = max_int;

for(int i=0,j=0;i+j<m;)
{
    if(a[i+1]+b[j] < a[i]+b[j+1])
    {
        c[i+j] = a[i+1]+b[j];
        i++;
    }
    else
    {
        c[i+j] = a[i]+b[j+1];
        j++;
    }
}

Answer 2

Я не даю вам ответ, но вот несколько советов, которые заставят вас думать в правильном направлении.

Итак, скажем, у вас есть.Имейте в виду, что эти списки уже отсортированы, это очень важно.{a1, a2, a3} {b1, b2, b3}

Как вы правильно сказали, первый элемент - это a1 + b1.Зачем?Потому что это самые маленькие числа в обоих массивах, поэтому их сумма будет самой маленькой.

Какие варианты у вас есть для второго элемента?Помните, что список отсортирован!Это может быть a1 + b2?Это может быть a1 + b3?И наоборот, это может быть b1 + a2?Это может быть b1 + a3?

Может ли это быть b2 + a2?(два ответа «да» и три ответа «нет» выше)

Используя это, вы сможете понять, как найти второй наименьший элемент, и отсюда должно быть легко найти, как это сделать для всех элементов.

Если вы все еще в замешательстве, задавайте вопросы в комментариях.

GL!

Answer 3

Это распространенная домашняя проблема. Поскольку массивы A и B отсортированы, вы можете выполнить парное слияние, почти как сортировка слиянием, с той лишь разницей, что вы пытаетесь сравнивать суммы, а не сами числа. Другими словами, скажем, ваши указатели в данный момент находятся в A_i и B_j, и вы просто добавили A_i + B_j в список C. Следующий элемент может быть A_i + B_ {j + 1} или это может быть A_ {i + 1} + B_j , Просто посмотрите, что меньше, а затем переместите указатель вперед.

Кажется, вы уже на нем, и ответ другого пользователя (или, скорее, вопросы!), Должно быть, уже направил вас в правильном направлении, но если у вас есть еще вопросы, не стесняйтесь спрашивать.

[PS: нет причин бояться дубликатов в массивах A, B или C. Дубликаты ничего не меняют для этого вопроса. Считайте структуру данных списком, а не множеством.]

Answer 4

Найдите наименьший элемент в A (назовем его a) и наименьший элемент в B (b).Наименьший элемент в C - это + b.

Если вам нужна позиция этого элемента в C и если первый элемент a1 + b1, второй a1 + b2 и т. Д., То позиция искомого элемента будет pos(a) * size(B) + pos(b).