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

Question

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

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

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

Answer 1

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

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

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

Answer 2

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