[Описание] Для двух целых массивов с одинаковой длиной. Разработайте алгоритм, который может судить о том, совпадают ли они. Определение "того же" состоит в том, что если эти два массива были отсортированы по порядку, элементы в соответствующем положении должны быть одинаковыми.
[Example]
<1 2 3 4> = <3 1 2 4>
<1 2 3 4> != <3 4 1 1>
[Ограничение] Алгоритм должен требовать постоянного дополнительного пространства и времени выполнения O (n).
(Вероятно, слишком сложный вопрос для интервью.)
(Вы можете использовать время O (N), чтобы проверить, что min, max, sum, sumsq и т.д. сначала равны.)
Используйте no-extra-space radix sort для сортировки двух массивов на месте. O (N), O (1) пространство.
Затем сравните их, используя обычный алгоритм. O (N), O (1) пространство.
(При условии, что (max & min; min) массивов имеет O (N k) с конечным k.)
Вы можете попробовать вероятностный подход - преобразовать массивы в число в некоторой огромной базе B и mod некоторым простым P, например sum B^a_i для всех i mod some big-ish P. Если они оба выйдут на один и тот же номер, повторите попытку за столько простых чисел, сколько захотите. Если это неверно при любых попытках, то они неверны. Если они пройдут достаточно сложных задач, то они с большой вероятностью будут равны.
Существует тривиальное доказательство для B > N, P > наибольшего числа. Таким образом, должен быть вызов, который не может быть удовлетворен. Это фактически детерминированный подход, хотя анализ сложности может быть более сложным, в зависимости от того, как люди рассматривают сложность с точки зрения размера ввода (в отличие от количества элементов).
Я утверждаю, что: если не задан диапазон ввода, то он НЕВОЗМОЖНО решить в дополнительном пространстве и времени O (n).
Я буду рад, что оказался ошибочным, чтобы я мог узнать что-то новое.
Хорошо, это не с постоянным дополнительным пространством, но лучше всего я мог бы подняться на данный момент:-). Существуют ли какие-либо другие ограничения, налагаемые на вопрос, например, например, на наибольшее целое число, которое может быть включено в массив?
Несколько ответов в основном правильны, хотя они не похожи. Подход хэш-таблицы (для одного примера) имеет верхний предел, основанный на диапазоне используемого типа, а не на количестве элементов в массивах. По крайней мере, по большинству определений, что делает (верхний предел) пространством постоянным, хотя константа может быть довольно большой.
В теории вы можете изменить это с верхнего предела на истинное постоянное количество пространства. Например, если вы работали на C или С++, и это был массив char, вы могли бы использовать что-то вроде:
size_t counts[UCHAR_MAX];
Поскольку UCHAR_MAX является константой, объем пространства, используемого массивом, также является константой.
Изменить: я хотел бы отметить для записи, что привязка к диапазонам/размерам задействованных элементов подразумевается почти во всех описаниях алгоритмической сложности. Например, мы все "знаем", что Quicksort - это алгоритм O (N log N). Это правда, однако, если мы предположим, что сравнение и замена сортируемых элементов занимает постоянное время, что может быть истинным только в том случае, если мы связали диапазон. Если диапазон задействованных элементов достаточно велик, и мы больше не можем рассматривать сравнение или обмен как постоянное время, то его сложность станет чем-то вроде O (N log N log R), если R - диапазон, поэтому log R аппроксимирует количество бит, необходимых для представления элемента.
Это трюк? Если авторы предполагали, что целые числа находятся в заданном диапазоне (2 ^ 32 и т.д.), Тогда "дополнительное постоянное пространство" может быть просто массивом размера 2 ^ 32, в котором вы считаете вхождения в обоих списках.
Если целые числа не изменяются, это невозможно.
Вы можете добавить каждый элемент в hashmap < Integer, Integer > со следующими правилами: Array A - сумматор, массив B - это средство удаления. При вставке из Array A, если ключ не существует, вставьте его со значением 1. Если ключ существует, увеличьте значение (сохраните счет). При удалении, если ключ существует и больше 1, уменьшите его на 1. Если ключ существует и равен 1, удалите элемент.
Запустите массив A, за которым следует массив B, используя приведенные выше правила. Если в любое время во время фазы удаления массив B не находит элемент, вы можете немедленно вернуть значение false. Если после того, как оба сумматора и удаления закончены, hashmap пуст, массивы эквивалентны.
Изменить: размер хэш-таблицы будет равен количеству различных значений в массиве, соответствует ли это определению константного пространства?
Я предполагаю, что для решения потребуется какое-то преобразование, которое является ассоциативным и коммутативным и гарантирует уникальный результат для уникального набора входов. Однако я не уверен, что это даже существует.
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;
}
Для каждого массива используйте метод сортировки подсчета, чтобы построить счетчик количества элементов, меньших или равных определенному элементу. Затем сравните два построенных вспомогательных массива с каждым индексом, если они равны массивам r, равным другим, а не r. Для сортировки COACH требуется O (n) и сравнение массива при каждом индексе снова O (n), так что полностью его O (n), а требуемое пространство равно размеру двух массивов. Вот ссылка на подсчет сортировки http://en.wikipedia.org/wiki/Counting_sort.
данный 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)
Аккумулятор должен иметь возможность хранить целое число с диапазоном = + - arraysize * n
Как это сделать - XOR все числа в обоих массивах. Если результат равен 0, вы получили совпадение.