Этап 1: учитывая два массива, скажем A [] и B [], как вы могли бы узнать, находятся ли элементы B в A?
Этап 2. Как насчет размера A [] составляет 10000000000000... и B [] намного меньше этого?
Этап 3. Как насчет размера B [] также 10000000000.....?
Мой ответ таков:
Этап 1:
Этап 2: используя бит-набор, поскольку целое число равно 32 бит....
Этап 3:..
Есть ли у вас хорошие идеи?
hash все элементы в A [перебираем массив и вставляем элементы в хэш-набор], затем итерации B и проверяем каждый элемент, если он находится в B или нет. вы можете получить среднее время выполнения O(|A|+|B|).
Вы не можете получить сублинейную сложность, поэтому это решение оптимально для анализа среднего случая, однако, поскольку хеширование не O(1) наихудшего случая, вы можете получить плохая производительность в худшем случае.
EDIT:
Если у вас недостаточно места для хранения хеш-набора элементов в B, вам может потребоваться определить вероятностное решение с помощью bloom filters. Проблема: могут быть некоторые ложные срабатывания [но никогда не ложные отрицательные]. Точность правильного увеличения увеличивается, поскольку вы выделяете больше места для фильтра цветения.
Другое решение, как вы сказали, sort, которое будет O(nlogn) time, а затем использовать двоичный поиск для всех элементов в B в отсортированном массиве.
Для 3-го этапа вы получаете такую же сложность: O(nlogn) с тем же решением, это займет примерно два раза, а затем на этапе 2, но все же O(nlogn)
EDIT2:
Обратите внимание, что вместо обычного хэша иногда вы можете использовать trie [зависит от типа ваших элементов], например: для ints, сохраните номер, поскольку это была строка, каждая цифра будет похожа на символ. с этим решением вы получаете решение O(|B|*num_digits+|A|*num_digits), где num_digits - количество цифр в ваших номерах [если они являются ints]. Предполагая, что num_digits ограничено конечным размером, вы получаете O(|A|+|B|) худший случай.
Этап 1: создает хэш-набор из A и выполняет итерацию по B, проверяя, существует ли текущий элемент B[i] в A (так же, как предложенный ранее @amit). Сложность (усредненная) - O (длина (A) + длина (B)).
Этап 2: делает хэш-набор от B, затем перебирает A и если текущий элемент существует в B, удаляет его от B. Если после итерации B имеет не менее 1 элемент, то не все B элементы существуют в A; иначе A является полным надмножеством B. Сложность (усредненная) - O (длина (A) + длина (B)).
Этап 3: сортируйте оба массива на месте и итерации, ищите те же цифры в текущих позициях i и j для A[i] и B[j] (идея должна быть очевидной). Сложность - O (n * log n), где n = длина (A).