Сравните два целочисленных массива с той же длиной

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

Теоретически вы можете изменить это значение с верхнего предела на истинное постоянное количество пространства. Например, если вы работали на C или C ++, и это был массив из char , вы могли бы использовать что-то вроде:

size_t counts[UCHAR_MAX];

Поскольку UCHAR_MAX является константой, объем пространства, используемого массивом также является константой.

Изменить: я бы отметил для записи, что ограничение на диапазоны / размеры задействованных элементов подразумевается почти во всех описаниях алгоритмической сложности . Например, мы все «знаем», что Quicksort - это алгоритм O (N log N). Однако это верно только в том случае, если мы предположим, что сравнение и замена сортируемых элементов занимает постоянное время, что может быть правдой только в том случае, если мы ограничим диапазон.Если диапазон задействованных элементов достаточно велик, чтобы мы больше не могли рассматривать сравнение или обмен как занимающие постоянное время, то его сложность стала бы примерно такой, как O (N log N log R), если R - это диапазон, поэтому log R приближает количество битов, необходимых для представления элемента.

Вы можете попробовать вероятностный подход - преобразовать массивы в число с некоторой огромной базой B и модифицировать некоторым простым числом P , например суммой B ^ a_i для всех и мод некоторых больших P . Если они оба дают одно и то же число, попробуйте еще раз для любого количества простых чисел. Если при любых попытках он оказывается ложным, значит, они неверны. Если они пройдут достаточно испытаний, то они равны, с высокой вероятностью .

Существует тривиальное доказательство для B > N , P > наибольшего числа. Так что должна быть проблема, которую невозможно решить. На самом деле это детерминированный подход, хотя анализ сложности может быть более трудным, в зависимости от того, как люди воспринимают сложность с точки зрения размера входных данных (в отличие от просто количества элементов).

данные int находятся в диапазоне -n .. + простой способ проверки эквити может быть следующим (псевдокод):

// a & b are the array
accumulator = 0
arraysize = size(a)
for(i=0 ; i < arraysize; ++i) {
  accumulator = accumulator + a[i] - b[i]
  if abs(accumulator) > ((arraysize - i) * n) { return FALSE }
}
return (accumulator == 0)

аккумулятор должен иметь возможность хранить целое число с range = + - arrayize * n

Для каждого массива используйте метод сортировки «Подсчет», чтобы подсчитать количество элементов, меньшее или равное определенному элементу. Затем сравните два построенных вспомогательных массива по каждому индексу, если они r равны, массивы r равны, иначе r нет. Для сортировки COunting требуется O (n), а сравнение массивов по каждому индексу снова O (n), поэтому полностью его O (n), а необходимое пространство равно размеру двух массивов. Вот ссылка на счетную сортировку http://en.wikipedia.org/wiki/Counting_sort .

Это вопрос с подвохом? Если авторы предполагали, что целые числа находятся в заданном диапазоне (2 ^ 32 и т. Д.), То «дополнительное постоянное пространство» может быть просто массивом размером 2 ^ 32, в котором вы подсчитываете вхождения в обоих списках.

Если целые числа не ранжированы, это невозможно.

Я утверждаю, что: Если диапазон входных данных не указан, НЕВОЗМОЖНО решать в постоянном дополнительном пространстве и времени выполнения O (n).

Я буду счастлив, если мне покажут, что я неправ, и я смогу узнать что-то новое.

1. Вставить все элементы из первого массива в хеш-таблицу
2. Попытаться вставить все элементы из второго массива в одну и ту же хеш-таблицу - для каждой вставки в элемент уже должен быть там

Хорошо, это не с постоянным лишним пространством, но лучшее, что я мог придумать на данный момент :-). Существуют ли какие-либо другие ограничения на вопрос, например, наибольшее целое число, которое может быть включено в массив?

(Возможно, слишком сложный для вопроса на собеседовании.)

(Вы можете использовать время O (N), чтобы проверить min, max, sum, sumsq и т. д. равны первыми.)

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

Затем сравните их, используя обычный алгоритм. O (N) временная сложность, O (1) пространство.

(При условии (макс. - мин.) Массивов O (N ^k ) с конечным k.)

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

Вы можете добавить каждый элемент в хэш-карту со следующими правилами: массив A - сумматор, массив B - удалитель. При вставке из массива A, если ключ не существует, вставьте его со значением 1. Если ключ существует, увеличьте значение (ведите счет). При удалении, если ключ существует и больше 1, уменьшите его на 1. Если ключ существует и равен 1, удалите элемент.

Выполнить массив A, за которым следует массив B, используя приведенные выше правила. Если в любой момент во время фазы удаления массив B не находит элемент, вы можете сразу вернуть false. Если после того, как сумматор и удалитель закончили работу, хэш-карта пуста, массивы эквивалентны.

Изменить: размер хеш-таблицы будет равен количеству различных значений в массиве. Подходит ли это к определению постоянного пространства?

Как насчет этого - XOR для всех чисел в оба массива. Если результат 0, значит совпадение.