выяснить, содержат ли два массива один и тот же набор целых чисел без лишнего места и быстрее, чем NlogN
Я наткнулся на этот пост , в котором сообщается следующий вопрос интервью:
Учитывая два массива чисел, найдите, есть ли у каждого из двух массивов тот же набор целых чисел? Предложите алгоритм, который может работать быстрее, чем NlogN без лишнего пробела?
Лучшее, что я могу придумать, это следующее:
(a) отсортируйте каждый массив, а затем (b) установите два указателя, перемещающихся по двум массивам, и проверьте, не нашли ли вы разные значения .. .. но шаг (a) уже имеет сложность NlogN: (
(a) сканировать самый короткий массив и помещать значения в карту, а затем (b) сканировать второй массив и проверять, нашли ли вы значение, которого нет на карте. ..здесь у нас линейная сложность, но я использую лишнее пространство
... поэтому я не могу придумать решения для этого вопроса.
Идеи?
Спасибо за все ответы. Я чувствую, что многие из них правы, но я решил выбрать вариант руслика , потому что он дает интересный вариант, о котором я не думал.