Дано 2 больших статических массива: A
типа int []
и B
типа const int []
.
Как за линейное время дописать в A
все те элементы B
, которых нет в A
?
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуЗадача имеет тривиальное решение в виде урезанного варианта 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 нет повторяющихся элементов - то можно сделать следующее:
Все операции выполняются за O(n), соответственно общее время будет линейным.
char []
иconst char []
соответственно, то можно за линейное время