найти, если два массива содержат один и тот же набор целых чисел без дополнительного пробела и быстрее, чем NlogN

Question

Я наткнулся на этот пост , в котором сообщается следующий вопрос:

Учитывая два массива чисел, найдите, имеет ли каждый из двух массивов тот же набор целых чисел? Предложите алгоритм, который может работать быстрее, чем NlogN без лишних пробелов?

Лучшее, что я могу придумать, это следующее:

1. (a) отсортировать каждый массив, а затем (b) иметь два указателя, перемещающихся по двум массивам, и проверить, не находите ли вы разные значения ... но шаг (a) уже имеет сложность NlogN: (

2. (а) отсканировать кратчайший массив и поместить значения в карту, а затем (б) отсканировать второй массив и проверить, если вы найдете значение, которого нет на карте ... здесь мы имеем линейную сложность, но мы используем дополнительное пространство

... так что я не могу придумать решение этого вопроса.

Идеи

---

Спасибо за все ответы. Я чувствую, что многие из них правы, но я решил выбрать ruslik's , потому что это дает интересный вариант, о котором я даже не думал.

Answer 1

Вы можете попробовать вероятностный подход, выбрав коммутативную функцию для накопления (например, сложение или XOR) и параметризованную хеш-функцию.

unsigned addition(unsigned a, unsigned b);
unsigned hash(int n, int h_type);

unsigned hash_set(int* a, int num, int h_type){
    unsigned rez = 0;
    for (int i = 0; i < num; i++)
        rez = addition(rez, hash(a[i], h_type));
    return rez;
};

Таким образом, количество попыток до того, как вы решите, что вероятность ложного срабатывания будет ниже определенного порога, не будет зависеть от количества элементов, поэтому оно будет линейным.

РЕДАКТИРОВАТЬ : В общем случае вероятность того, что наборы одинаковы, очень мала, поэтому эту проверку O (n) с несколькими хэш-функциями можно использовать для предварительной фильтрации: решить как можно быстрее, если они безусловно, различны или если есть вероятность их эквивалентности, и если следует использовать медленный детерминистический метод. Конечная средняя сложность будет O (n), но в худшем случае сложность будет иметь детерминистский метод.

Answer 2

Вы сказали «без лишнего пробела» в вопросе, но я предполагаю, что вы на самом деле имеете в виду «с O (1) лишним пробелом».

Предположим, что все целые числа в массивах меньше к .Затем вы можете использовать радикальную сортировку по месту , чтобы отсортировать каждый массив за время O ( n log k ) с O (log *)1013 * k ) дополнительное пространство (для стека, как указано yi_H в комментариях), и сравните отсортированные массивы по времени O ( n log k ).Если k не зависит от n , то все готово.

Answer 3

Я предполагаю, что рассматриваемые целые числа имеют фиксированный размер (например, 32-разрядный).

Затем радикс-быстрая сортировка оба массива на месте (так называемая "двоичная быстрая сортировка")) является постоянным пространством и O (n).

В случае неограниченных целых чисел, я считаю (но не могу доказать, даже если это возможно), что вы не можете преодолеть барьер O (nk), где kколичество цифр наибольшего целого числа в любом массиве.

Лучше ли это, чем O (n log n), зависит от того, как предполагается, что k масштабируется с n, и, следовательно, зависит от того, что интервьюер ожидает от вас.

Answer 4

Особый, не сложный случай, когда один массив содержит 1,2, .., n.Это обсуждалось много раз:

• Как определить, является ли массив перестановкой в ​​O (n)?
• Алгоритм определения, является ли массивсодержит n ... n + m?
• mathoverflow

и, несмотря на многие попытки, не имеет детерминированных решений с использованием пространства O (1) и O (о) время было показано.Либо вы можете каким-то образом обмануть требования (повторно использовать пространство ввода, предположить, что целые числа ограничены), либо использовать вероятностный тест.

Возможно, это открытая проблема.

Answer 5

В алгебраической модели дерева решений существуют известные нижние границы Omega (NlogN) для вычисления пересечения множества (независимо от пределов пространства).

Например, см. Здесь: http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/06-algebraic-tree.pdf

Таким образом, если вы не выполняете хитрые битовые манипуляции / подходы типа хэширования, вы не можете добиться большего успеха, чем NlogN.

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

Answer 6

Обычным предположением для подобных проблем является тэта (log n) -битные слова, потому что это минимум, необходимый для индексации ввода.

1. Ответ полиномиальной оценки sshannin работает отличнонад конечными полями, что обходит трудности с регистрами ограниченной точности.Все, что нам нужно, это простое число соответствующего (легко найти при тех же предположениях, которые поддерживают много криптообеспечения с открытым ключом) или неприводимый многочлен в (Z / 2) [x] соответствующей степени (сложность здесь заключается в умножении многочленовбыстро, но я думаю, что алгоритм будет o (n log n)).

2. Если мы можем изменить вход с ограничением, что он должен поддерживать тот же набор, то это не слишкомТрудно найти место для радикальной сортировки.Выберите (n / log n) -й элемент из каждого массива и разделите оба массива.Сортируйте кусочки по размеру (n / log n) и сравнивайте их.Теперь используйте основную сортировку по размеру (n - n / log n).Из ранее обработанных элементов мы можем получить n / log n битов, где бит i включен, если a [2 * i]> a [2 * i + 1], и выключен, если a [2 * i]

Answer 7

Вот алгоритм co-rp:

В линейном времени итерируйте по первому массиву (A), создавая полином Pa = A [0] - x) (A [1] -x)... (A [n-1] - x).Сделайте то же самое для массива B, назвав этот полином Pb.

Теперь мы хотим ответить на вопрос: «Является ли Pa = Pb?»Мы можем проверить это вероятностно следующим образом.Выберите случайным образом число r из диапазона [0 ... 4n] и вычислите d = Pa (r) - Pb (r) за линейное время.Если d = 0, вернуть true;в противном случае верните false.

Почему это действительно?Прежде всего, обратите внимание, что если два массива содержат одинаковые элементы, то Pa = Pb, поэтому Pa (r) = Pb (r) для всех r.Имея это в виду, мы можем легко увидеть, что этот алгоритм никогда не будет ошибочно отклонять два одинаковых массива.

Теперь мы должны рассмотреть случай, когда массивы не идентичны.По лемме Шварта-Циппеля P (Pa (r) - Pb (r) = 0 | Pa! = Pb) <(n / 4n).Таким образом, вероятность того, что мы примем два массива как эквивалентные, когда они не равны <(1/4).</p>

Answer 8

почему бы мне не найти сумму, произведение, xor всех элементов одного массива и сравнить их с соответствующим значением элементов другого массива ??

xor элементов обоих массивов может датьноль, если он похож на

2,2,3,3 1,1,2,2

но что если вы сравните xor элементов двухмассив будет равен ???

рассмотрим это

10,3 12,5

здесь xor обоих массивов будет одинаковым !!!(10 ^ 3) = (12 ^ 5) = 9, но их сумма и произведение различны.Я думаю, что два разных набора элементов не могут иметь одинаковую сумму, произведение и xor!Это можно проанализировать с помощью простого анализа битовых значений.Что-то не так в этом подходе ??

Answer 9

Просто думал, есть ли способ, которым вы могли бы хэшировать кумулятивные значения обоих массивов и сравнивать их, предполагая, что функция хеширования не производит столкновения из двух разных шаблонов.

Answer 10

Все, что я знаю, это то, что сортировка на основе сравнения не может быть быстрее, чем O (NlogN), поэтому мы можем исключить большинство "общих" сортировок на основе сравнения. Я думал о том, чтобы сделать сортировку ведром. Возможно, если бы этот вопрос был задан в интервью, лучшим ответом было бы сначала уточнить, какие данные представляют эти целые числа. Например, если они представляют возраст людей, то мы знаем, что диапазон значений int ограничен, и можем использовать сортировку по сегментам в O (n). Однако этого не будет ...