Создайте объединение двух строковых массивов, не имея дубликатов

Question

Я только что написал свой экзамен, и один из вопросов хотел, чтобы мы получили объединение A [] размера N и B [] размера N и удалили дубликаты (A и B могут иметь дубликаты внутри себя) и поместили их в Z [ ] размер 2N. Мы просто попросили псевдокод для этого, но это класс C ++.

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

Тот, с ограничениями, который я смог сделать только O (N ^ 2) с гнездом для цикла и просто итерацией по Z [], когда я помещал элементы в Z из A и B.

Это был тот, кого меня больше интересовало мнение вашего парня / что бы вы сделали (для безлимитного):

Я получил следующее (Время выполнения O (NlogN)):

Создание массива E размером 2N Поместите все из A и B в E - O (N)

Объединить сортировку E // Использовать ascii для сортировки - O (NlogN) * ​​1013 *

String previous

for loop from i = 0 to sizeOfE  { - O(N)

if previous does not equal E[i] then add to Z[] and the string previous equals E[i] - O(1)

}

Это самый быстрый способ / это правильно? Как бы вы справились с этой проблемой?

Answer 1

Для первого варианта я бы просканировал A, чтобы найти значение, для которого половина значений ниже, а половина выше. Затем я поместил бы это значение в середину, а нижние значения - слева, а верхние - справа, а также выбросил бы все совпадающие значения. Это можно сделать без создания нового массива. Тогда я бы повторил на двух подмассивах. Это модифицированная быстрая сортировка, поэтому она O (nlog (n))

Тогда я бы повторил с B.

Тогда я бы слил два в Z, операция O (n), но слияние двух пропустило бы значение, если значение из A совпадает со значением из B.

Так что все это O (nlog (n)).

Для одного без ограничений я бы выполнил прямую сортировку слиянием для A, а затем B, за исключением того, что при объединении вы пропускаете значение, если оно соответствует предыдущему вставленному значению, и делаете это на протяжении всей сортировки слиянием. Это немного быстрее, поскольку в некоторых случаях дубликаты удаляются быстрее. В целом сортировка слиянием также O (nlog (n)).