Способ судить, идентичны ли два массива?

Question

Под identical Я имею в виду, что два массива содержат одинаковые элементы, порядок элементов в массивах здесь не имеет значения.

Решение, которое я придумал, выглядит следующим образом (, что, как указано в комментариях , является неправильным подходом):

<code><del> if the size of two Arrays are equal
 See True, find all elements of Array A in Array B
 All Found,  find all elements of Array B in Array A
 All Found, then I get conclusion two Arrays are identical</del>

Однако, есть ли лучший алгоритм с точки зрения сложности времени?

Answer 1

Допустим, у вас есть User[] массив 1 и User[] массив 2. Вы можете пролистать массив один и добавить их в словарь Dictionary<User, int>, где ключом является пользователь, а значением является счетчик. Затем вы перебираете второй массив и для каждого пользователя в массиве 2 уменьшаете счетчик в словаре (если счетчик больше 1) или удаляете элемент (если счетчик равен 1). Если пользователь отсутствует в словаре, вы можете остановиться, массивы не совпадают.

Если вы дошли до конца и ранее проверили, что длина массивов одинакова, то массивы совпадают. Если вы не проверили длину ранее (что, конечно, вам еще нужно было), то вы можете просто проверить, что словарь теперь пуст после полного цикла в массиве 2.

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

Answer 2

Моя идея состоит в том, чтобы пройтись по первому массиву и искать элементы во втором массиве.Конечно, единственная проблема заключается в том, что вы не можете использовать элемент во втором массиве дважды.Итак, создайте третий массив логических значений.Этот массив указывает, какие элементы в массиве 2 «были использованы».

Цикл по первому массиву.Внутри этого цикла просматривайте каждый элемент во втором массиве, чтобы увидеть, можете ли вы «найти» этот элемент во втором массиве, но также проверьте третий массив, чтобы убедиться, что позиция во втором массиве не использовалась.Если вы нашли совпадение, обновите эту позицию в третьем массиве и продолжайте.

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

OfКонечно, прежде чем начать все это, убедитесь, что длины одинаковы.

Answer 3

Ваш подход не работает, так как он рассматривал бы [0, 1, 1] как равный [0, 0, 1]. Каждый элемент в A находится в B и наоборот. Вам нужно будет посчитать количество вхождений каждого элемента в A и B. (Тогда вам не нужно , конечно, нужно сделать и то и другое, если вы уже проверили длины.)

Если содержимое можно сортировать, вы можете отсортировать и то, и другое, конечно же, сравнить поэлементно. Это работает, только если вы можете обеспечить общий порядок элементов.

Answer 4

Сначала проверьте размер двух массивов.Если они не равны, то они не содержат одинаковые элементы.

После этого отсортируйте оба массива по O (n lg (n)).Теперь просто проверьте оба массива поэлементно в O (n).Поскольку они отсортированы, если они равны, то они будут равны в каждой позиции.

Answer 5

Сортируйте оба массива в соответствии со строгим порядком и сравнивайте их по точкам.

---

Обновление: Суммируя некоторые из вопросов, которые были подняты, здесь эффективностьобычно можно ожидать:

• доступно строгое упорядочение: O (log N) для сортировки плюс сравнение по точкам
• доступно равенство и хеш-функция: сравните счетчики хэшей-термин, плюс фактические сравнения объектов в случае коллизий хэшей.
• только равенство, хэширование недоступно: необходимо считать каждый элемент или копировать один контейнер и удалять (эффективность зависит от контейнера).

Сложность сравнения по точкам линейна в положении первого несоответствия.

Answer 6

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

РЕДАКТИРОВАТЬ: Зависит от определения проблемы.Это решение будет работать тогда и только тогда, когда его оригинальное решение будет работать, а если массивы могут иметь дублирующиеся элементы, а вы не будете считать или помечать их как «использованные», это не сработает.

Answer 7

Если вы не возражаете против дополнительного пространства, вы можете сделать что-то вроде HashMap, чтобы сохранить пары (element, count) первого массива, а затем проверить, совпадает ли второй массив;это будет линейным по N (размер самого большого массива)