Программа C++ для проверки равенства двух массивов или нет
Имея два массива arr1[] и arr2[] длины N и M соответственно, задача состоит в том, чтобы проверить, равны ли два массива или нет.
Примечание. Говорят, что массивы равны тогда и только тогда, когда оба массива содержат одни и те же элементы и частоты каждого элемента в обоих массивах одинаковы.
Примеры:
Input: arr1[] = {1, 2, 3, 4, 5}, arr2[] = {5, 4, 3, 2, 1}
Output : Equal
Explanation: As both the arrays contain same elements.Input: arr1[] = {1, 5, 2, 7, 3, 8}, arr2[] = {8, 2, 3, 5, 7, 1}
Output : Equal
Наивный подход: основной способ решения проблемы заключается в следующем:
Apply sorting on both the arrays and then match each element of one array with the element at same index of the other array.
Следуйте шагам, указанным ниже, чтобы реализовать идею.
- Проверьте, равны ли длины обоих массивов или нет
- Затем отсортируйте оба массива, чтобы мы могли сравнить каждый равный элемент.
- Линейно перебрать оба массива и проверить, равны ли элементы или нет,
- Если равно, выведите Равно, а если нет, то выведите Не равно.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N * logN)
Вспомогательное пространство: O(1)
Эффективный подход: проблему можно эффективно решить с помощью хеширования (unordered_map),
Use hashing to count the frequency of each element of both arrays. Then traverse through the hashtables of the arrays and match the frequencies of the elements.
Выполните указанные ниже шаги, чтобы решить проблему:
- Проверьте, равны ли длины обоих массивов или нет
- Создайте неупорядоченную карту и сохраните все элементы и частоту элементов arr1[] на карте.
- Перейдите через arr2[] и проверьте, совпадает ли количество каждого элемента в arr2[] с количеством в arr1[] . Это можно сделать, уменьшив частоту при переходе в arr2[] .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(N)