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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Импортируем изображения через wysiwyg

Декабрь 27, 2014 г.

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

Читать

Генератор "удобных" паролей

Декабрь 19, 2012 г.

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

Читать

 

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