Библиотека C находит разницу между двумя массивами

Question

Учитывая 2 массива, мне нужна функция / библиотека C, которая найдет разницу между 2 массивами.

array1[] ={"a","b","c","e"}
array2[] ={"a","c","e"}

, и функция должна вернуть

{"b"}

Эти 2 массива гарантировано для сортировки, но не одного размера.Мне просто нужно, чтобы эта функция была быстрой.

Answer 1

Вот алгоритм O (n):

Создайте два указателя, каждый из которых инициализируется так, чтобы указывать на первый элемент каждого массива.Каждый раз, когда * p1 <* p2, добавляйте * p1 к выходному массиву и увеличивайте p1.То же самое для p2.Если они равны, увеличьте оба. </p>

Я оставлю вас, чтобы выяснить, как обрабатывать дубликаты элементов и что делать, когда один указатель достигает конца своего массива.

[Также, если вы можете использовать C ++, тогда вы должны просто использовать std :: set_symmetric_difference .]

Answer 2

@ Оли Чарльзуорт

if arr1 [] = {"a", "b", "c"} и arr2 [] = {"d", "e", "f"}

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