Поиск дубля в массиве на PHP

Оказывается, очень частая задача в тестовых заданиях соискателей — это поиск дубля в массиве. В зависимости от нюансов конкретного задания, могут просить:

  • найти все дубли или один единственный дубль;
  • использовать в решении самый быстрый алгоритм;
  • найти вообще все повторяющиеся варианты.

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

Итак, пусть $A — произвольный массив чисел. Напишем функцию, которая ищет близнеца или возвращает FALSE.

Скоростной вариант

Самый первый и самый быстрый вариант поиска — это положиться только на функции PHP без каких либо свои циклов и ветвлений.

Мы посчитали число значений, а потом просто вывернули массив. Если дублей было несколько — останется только один. Если нужно другое число повторений — используйте другой ключ на выходе (не 2, а 3, 4..).

PHP гораздо быстрее работает внутри собственных откомпилированных функций, нежели с вашими алгоритмами, какими бы они не были гениальными.

Вариант с сортировкой

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

Так мы обнаружим любое повторяющееся произвольное число раз значение (т.е. тройняшек,  и т.д.)

Если по условиям задачи массив уже отсортирован, то sort() можно убрать. Останется сканер массива, быстродействие которого линейно зависит от размеров массива.

В среднем, этот вариант в 2-3 раза медленнее предыдущего (на диапазоне от 1к до 100 к элементов).

Перекладываем из одной корзины в другую

Самый тормозной, неэффективный из трех.

Мы перебираем вх. массив ($A), складывая элементы в другой ($B). Но если в нем ($B) уже есть искомое значение, то вуаля! мы нашли близнеца.

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

Этот вариант  на 2 порядка хуже первого решения.

Если у вас есть другие варианты — присылайте :).

Написать комментарий

Мало букафф? Читайте есчо !

Работаем с датами широкого диапазона в PHP

Январь 28, 2016 г.

Многие не задумываются при работе в PHP со стандартными функциями даты-времени о диапазоне их применимости (date(), time(), mktime() и т.п). Так мы можем скоро столкнуться с проблемой, подобная которой случалась уже раньше - "ошибка 2000". Я прекрасно ...

Читать

Как определить ip адрес посетителя сайта в PHP

Ноябрь 13, 2015 г.

PHP не имеет каких то специальных средств для определения ip адреса. Эту информацию ему поставляет веб-сервер в виде переменных окружения. Используя ...

Читать

 

Комментарии к «Поиск дубля в массиве на PHP»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: