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

Ответ 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;
};

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

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

Ответ 2

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

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

Ответ 3

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

Затем radix-quicksorting оба массива на месте (он же "двоичный quicksort" ) - это постоянное пространство и O (n).

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

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

Ответ 4

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

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

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

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

Ответ 5

Вот алгоритм 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) (П/4n). Таким образом, вероятность того, что мы принимаем два массива как эквивалентные, когда они не являются, равна < (1/4).

Ответ 6

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

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

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

Ответ 7

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

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

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

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

Ответ 8

Вы можете разбить барьер O (n * log (n)), если у вас есть некоторые ограничения на диапазон чисел. Но это невозможно сделать, если вы не можете использовать дополнительную память (вам действительно нужны глупые ограничения, чтобы иметь возможность сделать это).

Я также хотел бы отметить, что даже O (nlog (n)) с сортировкой не является тривиальным, если у вас ограниченное пространство O (1), поскольку сортировка слияния использует O (n) пространство и quicksort (что даже не строгое o (nlog (n)) требует O (log (n)) пространства для стека. Вы должны использовать heapsort или smoothsort.

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

Проверьте этот вопрос на пару хороших методов: Алгоритм, чтобы определить, имеют ли два массива одинаковые элементы

Ответ 9

Для каждого целого числа i убедитесь, что количество вхождений i в двух массивах либо равно нулю, либо оба отличных от нуля, путем итерации по массивам.

Поскольку число целых чисел является постоянным, общая продолжительность выполнения O(n).

Нет, я бы не делал этого на практике.

Ответ 10

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

Ответ 11

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

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

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

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

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

10,3 12,5

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

Ответ 12

Я не уверен, что правильно понял проблему, но если вас интересуют целые числа, которые находятся в обоих массивах:

Если N → → > 2 ^ SizeOf (int) (количество бит для integer (16, 32, 64)), есть одно решение:

a = Array(N); //length(a) = N;
b = Array(M); //length(b) = M; 
//x86-64. Integer consist of 64 bits.

for i := 0 to 2^64 / 64 - 1 do  //very big, but CONST
  for k := 0 to M - 1 do
    if a[i] = b[l] then doSomething;   //detected

for i := 2^64 / 64 to N - 1 do
 if not isSetBit(a[i div 64], i mod 64) then
   setBit(a[i div 64], i mod 64);

for i := 0 to M - 1 do
 if isSetBit(a[b[i] div 64], b[i] mod 64) then doSomething; //detected

O (N), без наружных структур

Ответ 13

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

Ответ 14

Если массивы имеют одинаковый размер и гарантированно не будет дубликатов, суммируйте каждый из массивов. Если сумма значений различна, то они содержат разные целые числа.

Изменить: вы можете суммировать журнал записей в массивах. Если это тоже то же самое, то у вас есть те же записи в массиве.