Перестановка между двумя массивами друг друга?

Question

Можно создать дубликат:
Check if array B is a permutation of A

Учитывая 2 несортированные целые массивы a и b одинакового размера. Определите, является ли b перестановкой a. Можно ли это сделать в O(n) time и O(1) space?

Первое, что пришло мне в голову, это то, что используется XOR, то есть XOR all the elements of a and b and if the resultant is 0 which means that b is a permutation of a. Но он приводит примеры, когда этот подход терпит неудачу. Для например -

a: [1 6 0 0 4] -- b: [1 0 6 1 5] 
a: [1 6 0 0 5] -- b: [1 0 6 1 4] 

Любое одно имея ни малейшего представления, что, как это сделать в O(n) time и O(1) space?

Answer 1

Если набор элементов неотрицательны, и у вас есть неограниченный целочисленный тип (а BigInteger или аналогичный) доступны, можно определить функцию по набору A:

C(A) = product(p_(a+1))) для каждого a в A

где p_n - n -е простое число. Тогда C зависит только от значений от A, а не их порядка; и любое изменение значений изменяется C.

Например,

C([1 6 0 0 4]) = p_2.p_7.p_1.p_1.p_5 = 3.17.2.2.11 = 2244 

(и, очевидно, любой набор с теми же элементами имеет тот же C, независимо от заказа), и

C([1 6 0 1 4]) = p_2.p_7.p_1.p_2.p_5 = 3.17.2.3.11 = 3366 

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

Answer 2

В случае ограниченного диапазона целых чисел - пусть этот диапазон будет [n,m] таким образом, что m-n = U вы можете сортировать массивы с помощью in place radix sort, также обсуждается в this great post.

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

Примечание:
Там некоторые «обман» в этом ответе [таким образом, я не отправлял его, пока ОП не просил об этом в комментариях ..], так как временная сложность этого является O(nlogU), и пространство O(logU). Однако для ограниченных диапазонов мы можем считать O(logU) = O(1), и для этих случаев мы получаем O(n) время и O(1).

Answer 3

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

То, что вы хотите, это хэш-функция, которая ...

1. дает хэши, которые крайне вряд ли столкнутся, так что они могут рассматриваться в качестве уникальных идентификаторов для целых чисел. Git использует хеши SHA-1 для определения версий исходного кода, вероятность того, что вероятность столкновения настолько низка, что его можно игнорировать.

2. Коммутативный (например, xor и plus) и, вероятно, ассоциативный, поэтому порядок элементов не изменяет полученный хэш.

Это второе требование, вероятно, неловкое. Я провел немного времени в Google, но просто испугался таких слов, как «Quasigroup».