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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ноябрь 13, 2015 г.

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

Читать

Функция сравнения двух строк на PHP

Август 1, 2017 г.

Насколько похожи две строки? В PHP для выяснения подобия строк есть две функции - similar_text() и levenshtein(). Первая из них считает процент ...

Читать

 

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

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



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

Много комментариев в “Поиск дубля в массиве на PHP”

  1. Никита:

    Есть куда более простой способом.
    $array = array (1,2,3,3,3,2);
    $array_uniq = array_unique($array);

    print_r(array_diff_key($array, $array_uniq));

    • Спасибо, Никита. Тоже годный пример.
      Хотя первый вариант по-проще будет.
      И тут, видимо, ещё можно добавить как последний штрих — array_unique().

      function array_find_twins_Nikita_remix($A) {
      return array_unique(array_diff_key($A, array_unique($A)));
      }