Решение алгоритмических проблем: Поиск повторяющихся элементов в массиве
Этот пост является частью серии статей о том, как решать алгоритмические проблемы. Из собственного опыта, я понял, что большинство авторов просто пошагово расписывают решение проблемы. Отсутствие обобщённого представления о проблеме, не позволяет понять её и найти эффективное решение. Исходя из этого понимания, цель данной серии: описывать процессы рассуждений о том, как решать такие проблемы с нуля.
Проблема
- Найти дубликат в массиве
Процесс решения задачи
Перед тем как вы увидите решение, давайте немного поговорим о самой проблеме. У нас есть: массив n + 1 элементов с целочисленными переменными в диапазоне от 1 до n .
Например: массив из пяти integers подразумевает, что каждый элемент будет иметь значение от 1 до 4 (включительно). Это автоматически означает, что будет по крайней мере один дубликат.
Единственное исключение — это массив размером 1. Это единственный случай, когда мы получим -1.
Brute Force
Метод Brute Force можно реализовать двумя вложенными циклами:
O(n²) — временная сложность и O(1) — пространственная сложность.
Count Iterations
Другой подход, это иметь структуру данных, в которой можно перечитать количество итераций каждого элемента integer. Такой метод подойдёт как для массивов, так и для хэш-таблиц.
Реализация на Java:
Значение индекса i представляет число итераций i+1 .
Временная сложность этого решения — O(n), но и пространственная — O(n), так как нам требуется дополнительная структура.
Sorted Array
Если мы применяем метод упрощения, то можно попытаться найти решение с отсортированным массивом.
В этом случае, нам нужно сравнить каждый элемент с его соседом справа.
Реализация на Java:
Пространственная сложность O(1), но временная O(n log(n)), так как нам нужно отсортировать коллекцию.
Sum of the Elements
Ещё один способ — это суммирование элементов массива и их сравнение с помощью 1 + 2 + … + n.
В этом примере мы можем добиться результата временной сложности O(n) и пространственной O(1). Тем не менее, это решение работает только в случае, когда мы имеем один дубликат.
Такой способ приведёт в тупик. Но иногда, чтобы найти оптимальное решение, нужно перепробовать всё.
Marker
Кое-что интересное стоит упомянуть. Мы рассматривали решения, не учитывая условия, что диапазон значений integer может быть от 1 до n . Из-за этого примечательного условия каждое значение имеет свой собственный, соответствующий ему индекс в массиве.
Суть этого решения в том, чтобы рассматривать данный массив как список связей. То есть значение индекса указывает на его содержание.
Мы проходим через каждый элемент и помечаем соответствующий индекс, прибавляя к нему знак минус. Элемент является дубликатом, если его индекс уже помечен минусом.
Давайте рассмотрим конкретный пример, шаг за шагом:
Реализация на Java:
Это решение даёт результат временной сложности O(n) и пространственной O(1). Тем не менее, потребуется изменять список ввода.
Runner Technique
Есть ещё один способ, который предполагает рассматривать массив как некий список связей (повторюсь, это возможно благодаря ограничению диапазона значений элементов).
Давайте проанализируем пример [1, 2, 3, 4, 2] :
Такое представление даёт нам понять, что дубликат существует, когда есть цикл. Более того, дубликат проявляется на точке входа цикла (в этом случае, второй элемент).
Мы можем взять за основу алгоритм нахождения цикла по Флойду, тогда мы придём к следующему алгоритму:
- Инициировать два указателя slow и fast
- С каждым шагом: slow смещается на шаг со значением slow = a[slow] , fast смещается на два шага со значением fast = a[a[fast]]
- Когда slow == fast ― мы в цикле.
Можно ли считать этот алгоритм завершённым? Пока нет. Точка входа этого цикла будет обозначать дубликат. Нам нужно сбросить slow и двигать указатели шаг за шагом, пока они снова не станут равны.
Возможная реализация на Java:
Это решение даёт результат временной сложности O(n) и пространственной O(1) и не требует изменения входящего списка.
Поиск одинаковых элементов в массивах
Добрый вечер. Программа ищет в трёх массивах одинаковые для всех них элементы и вывести их количество. Я сделал это так:
Как можно ускорить(сократить время работы) программы?
Время работы Вашей программы na * nb * nc = O(n^3) . Можно отсортировать все массивы за O(n*log(n)) . Потом пройтись по всем массивам в одном цикле за линейное время. Итоговое время:
na*log(na) + nb*log(nb) + nc*log(nc) + na + nb + nc = O(n*log(n)) .
Я бы сделал так:
- Убрал бы декларацию int i, j, l при инициализации цикла и вынес их перед всеми циклами
- Объявил был i, j, l как register
- Третий цикл должен работать только когда a==b , иначе это бесполезный расход ресурсов
- Сравнил бы размеры na, nb и nc — самый внешний цикл мне кажется должен быть самым коротким
А если так? Считаем, что повторяющихся значений нет, или они не учитываются
Дизайн сайта / логотип © 2023 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2023.3.11.43300
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
Как найти дубликаты в массиве
Иногда возникает необходимость найти дубликаты в массиве. В данной статье мы расскажем, как это сделать двумя способами.
Задача
Итак, у нас есть массив. Это может быть массив любых объектов или примитивов. Для примера возьмём массив строк:
Теперь попробуем найти дублирующиеся строки в этом массиве.
Поиск дубликатов перебором
Сначала объявим вспомогательную коллекцию для хранения дубликатов – HashSet:
Каждый раз, находя дубликат в массиве, мы будет его класть в данный HashSet.
Далее мы будем проходить по элементам массива, используя два цикла. В первом цикле мы извлекаем элемент массива и поочерёдно сравниваем его с остальными элементами массива, используя второй цикл:
И в конце возвратим найденные дубликаты:
Проверка
Проверим нашу программу:
Исходный код
Заключение
На данном примере мы разобрали, как находить дубликаты в массиве. Это может быть массив любых объектов.
Найдите повторяющийся элемент в массиве с ограниченным диапазоном
Учитывая ограниченный диапазон размеров массива n содержащие элементы от 1 до n-1 с повторяющимся элементом найдите в нем повторяющийся номер, не используя лишнего пробела.
Input: < 1, 2, 3, 4, 4 >
Output: The duplicate element is 4
Input: < 1, 2, 3, 4, 2 >
Output: The duplicate element is 2
Подход 1: Использование хеширования
Идея состоит в том, чтобы использовать Хеширование Для решения этой проблемы. Мы можем использовать посещенный логический массив, чтобы отметить, был ли элемент замечен ранее или нет. Если элемент уже встречался ранее, посещенный массив вернет значение true.
Ниже приведена реализация на C++, Java и Python, основанная на приведенной выше идее:
результат:
The duplicate element is 4
результат:
The duplicate element is 4
Python
результат:
The duplicate element is 4
Временная сложность приведенного выше решения равна O(n) и требует O(n) дополнительное пространство, где n это размер ввода.
Подход 2: Использование индексов массива
Мы можем решить эту задачу в постоянном пространстве. Поскольку массив содержит все отдельные элементы, кроме одного, и все элементы лежат в диапазоне от 1 до n-1 , мы можем проверить наличие повторяющегося элемента, пометив элементы массива как отрицательные, используя индекс массива в качестве ключа. Для каждого элемента массива nums[i] , инвертировать знак элемента, присутствующего в индексе nums[i] . Наконец, еще раз пройдитесь по массиву, и если в индексе будет найдено положительное число i , то повторяющийся элемент i .
Приведенный выше подход требует двух обходов массива. Мы можем добиться того же только за один проход. Для каждого элемента массива nums[i] , инвертировать знак элемента, присутствующего в индексе nums[i] если он положительный; в противном случае, если элемент уже отрицательный, то это дубликат.