Есть способ сделать это в O (n), если вы хотите сделать копию одного из списков в другой структуре данных. Это классический компромисс между временем и пространством.
Создать хэш-карту списка R, где ключом является элемент, а значением - исходный индекс в массиве; в C ++ вы можете использовать unordered_map из tr1 или boost.
Сохранить индекс для необработанной части списка R, инициализированной для первого элемента.
Для каждого элемента в списке L, проверьте хеш-карту на совпадение в списке R. Если вы не нашли его, выведите (значение L, NULL). Если есть совпадение, получите соответствующий индекс из хэш-карты. Для каждого необработанного элемента в списке R вплоть до соответствующего индекса выведите (NULL, значение R). Для совпадения выведите (значение, значение).
Когда вы дойдете до конца списка L, просмотрите оставшиеся элементы списка R и выведите (NULL, значение R).
Редактировать: Вот решение в Python. Для тех, кто говорит, что это решение зависит от наличия хорошей функции хеширования - конечно, это так. Оригинальный постер может добавить дополнительные ограничения к вопросу, если это проблема, но я буду занимать оптимистическую позицию до тех пор.
def FindMatches(listL, listR):
result=[]
lookupR={}
for i in range(0, len(listR)):
lookupR[listR[i]] = i
unprocessedR = 0
for left in listL:
if left in lookupR:
for right in listR[unprocessedR:lookupR[left]]:
result.append((None,right))
result.append((left,left))
unprocessedR = lookupR[left] + 1
else:
result.append((left,None))
for right in listR[unprocessedR:]:
result.append((None,right))
return result
>>> FindMatches(('d'),('a','b','c'))
[('d', None), (None, 'a'), (None, 'b'), (None, 'c')]
>>> FindMatches(('a','b','c','d','e'),('b','q','c','d','g','e'))
[('a', None), ('b', 'b'), (None, 'q'), ('c', 'c'), ('d', 'd'), (None, 'g'), ('e','e')]