Задача собеседования: найти различные элементы в двух массивах

• Этап 1: Учитывая два массива, скажем, A [] и B [], как вы можете узнать, находятся ли элементы B в A?

• Этап 2: Как насчет размера A [] составляет 10000000000000 ... и B [] намного меньше этого?

• Этап 3: А размер B [] также равен 10000000000 .....?

Мой ответ следующий:

• Этап 1:

  1. двойной цикл for - O (N ^ 2);
  2. сортировка A [], затем двоичный поиск - O (NlgN)

• Этап 2: с использованием набора бит, поскольку целое число составляет 32 бита ....

• Этап 3: ..

Есть ли у вас какие-нибудь хорошие идеи?