Блог

Главная - Вопросы по программированию - Создайте объединение двух массивов строк, не имея дубликатов

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

#c #arrays #sorting #pseudocode

#c #массивы #сортировка #псевдокод

Вопрос:

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

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

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

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

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

Создайте массив E размером 2N, поместите все из A и B в E — O(N)

Сортировка слиянием E // Используйте ascii для сортировки — O(NlogN)

 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)

}

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

Комментарии:

1. Сортировка A и B , затем объединение в Z .

2. Я бы использовал векторы строк, сортировал их с помощью std::sort() и сохранял их объединение в третьем векторе, используя std::set_union() .

3. @Shawn: ты забываешь std::unique после std::sort .

Ответ №1:

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

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

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

Итак, все дело в O(nlog(n)) .

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

Метки: ,