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

Question

[Описание] Даны два целочисленных массива одинаковой длины. Разработайте алгоритм, который может оценить, одинаковы ли они. Определение «то же самое» состоит в том, что, если эти два массива были в отсортированном порядке, элементы в соответствующей позиции должны быть одинаковыми.

[Example]
<1 2 3 4>  = <3 1 2 4>
<1 2 3 4> != <3 4 1 1>

[Ограничение] Алгоритм должен требовать постоянного дополнительного пространства и времени работы O (n).

Answer 1

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

(Вы можете использовать время O (N), чтобы проверить, равны ли минимальные, максимальные, суммы, суммы и т. Д.)

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

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

(при условии (макс. И минус; мин) массивов O (N ^k ) с конечным k.)

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

size_t counts[UCHAR_MAX];

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

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

Answer 5

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

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

Answer 6

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

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

Answer 7

public static boolean match(int[] array1, int[] array2) {

        int x, y = 0;

        for(x = 0; x < array1.length; x++) {
                y = x;
                while(array1[x] != array2[y]) {
                        if (y + 1 == array1.length)
                                return false;
                        y++;
                }
                int swap = array2[x];
                array2[x] = array2[y];
                array2[y] = swap;
        }

        return true;
}

Answer 8

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

Answer 9

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

Answer 10

заданные значения int находятся в диапазоне -n .. + 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)

Аккумулятор

должен хранить целое число с диапазоном = + - размер массива * n