Симметричная разность двух массивов

У меня есть два объекта фильма, называемых DVD и VHS. Я бы хотел найти симметричную разницу этих массивов. Я хочу знать, какие фильмы в VHS покупают не на DVD, а какие фильмы находятся на DVD, но не в VHS.Симметричная разность двух массивов

Может ли кто-нибудь сказать мне, есть ли быстрый алгоритм для его решения (желательно в C или Objective-C)? Это быстрее/проще решить, если я использую словари? Что называется такой проблемой (или это просто «симметричная разница»)?

Спасибо.

источник

2010-02-18 nevan king

Вы можете получить лучшие результаты, используя NSSet, а не NSArray, в зависимости от того, разрешить ли вам дубликаты в ваших списках.

NSSet дает вам методы, как intersectsSet:, которые должны предоставить вам то, что вам нужно.

Если вам нужна функция объединения, вы можете использовать NSMutableSet.

источник

2010-02-18 12:01:39 Jasarien

Симметричная разность - это '(объединение B) минус (A пересекается B)' или эквивалентно, (A минус B) объединение (B минус A) '. – kennytm

В моих массивах нет дубликатов. 'intersectsSet:' кажется, возвращает только BOOL, сообщающий вам, пересекаются они или нет. Я ищу противоположность пересечения. Я просмотрел документы «NSSet», но не мог видеть такой метод, как тот, который мне нужен. –

Обратите внимание, что NSMutableSet имеет '-intersectSet:', который фактически удаляет объекты из приемника, чтобы преобразовать его в пересечение. –

Если вам нужны VHS минус DVD и DVD минус VHS в двух разных массивах, используйте -removeObjectsInArray:.

Если вы нуждаетесь в них как в одном массиве, сортируйте их и попробуйте повторно реализовать this algorithm в ObjC.

источник

2010-02-18 11:47:09 kennytm

Попробуйте отсортировать оба массива, используя Title of Movie (MergeSort), затем слейте их оба и измените функцию слияния, чтобы он печатал уникальные необычные элементы.

источник

2010-02-18 11:53:04 bhups

Это похоже на то, о чем я думал. Сортируйте массивы (у меня есть идентификаторы), затем одновременно выполняйте оба массива, сравнивая и находите совпадения или дыры/необычные элементы. Вы знаете, где я могу найти код для этого? Это называется сортировкой слияния? –

Да, это называется NergeSort. Вы можете найти множество примеров в сети. вот один из них: http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Merge_sort – bhups

Симметричная разность двух массивов

ответ

Смежные вопросы