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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проверка кодов ОГРН / ОГРНИП на PHP

Сентябрь 24, 2015 г.

Продолжая тему валидаторов, публикую код двух функций для проверки введенных пользователем кодов ОГРН или ОГРНИП. Проверка кода ОГРН. Код содержит 13 знаков, последний из них используется для проверки "контрольной суммы". [crayon-5c0ff91b49950716825236/] ...

Читать

Переводим строку в число с плавающей запятой в PHP

Май 7, 2018 г.

Скаляры для PHP все на одно лицо. Строки или числа, с плавающей запятой или без. PHP не заморачивается. Ему не нужны строгие рамки типов скаляра. Платить за эту вольность приходится довольно скоро. Начнем с того, что PHP знает два оператора сложения, ...

Читать

 

Комментарии к «Поиск дубля в массиве на 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)));
      }