0

Дано 2 больших статических массива: A типа int [] и B типа const int [].

Как за линейное время дописать в A все те элементы B, которых нет в A?

10
  • Задача бессмысленна, так как неограниченное нельзя пересчитать за ограниченное время.:) 12 дек 2015 в 20:23
  • @VladfromMoscow в смысле могут быть большими (чтобы видеть различия в скорости алгоритмов)
    – kulek
    12 дек 2015 в 20:24
  • За линейное время задание не выполнить. 12 дек 2015 в 20:28
  • @VladfromMoscow Почему так?
    – kulek
    12 дек 2015 в 20:32
  • 1
    @VladfromMoscow Если заменить типы массивов на char [] и const char [] соответственно, то можно за линейное время
    – kulek
    12 дек 2015 в 20:37

1 ответ 1

1

Задача имеет тривиальное решение в виде урезанного варианта counting sort, с использованием примерно 2^sizeof(int) дополнительной памяти.

vector<bool> has_number(max(A) + 1);
for (int x : A) has_number[x] = true;
for (int x : B) if (!has_number[x]) append(x);

Если нам не важен порядок элементов, и в A нет повторяющихся элементов - то можно сделать следующее:

  • дописываем весь B в конец A,
  • сортируем A за O(n) с помощью radix sort,
  • удаляем дубликаты.

Все операции выполняются за O(n), соответственно общее время будет линейным.

0

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.