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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Регистрация/авторизация в Drupal по учетке в соц.сетях

Май 12, 2013 г.

Самое не приятное, с чем можно встретиться на многих сайтах - это регистрация учетной записи. Неприятное ощущение усиливается ещё и от контраста - везде ...

Читать

Считаем полное число строк в запросе MySQL, ограниченного LIMIT

Ноябрь 2, 2012 г.

О полезном операторе - SQL_CALC_FOUND_ROWS. Это конструкция просто незаменима для организации постраничного вывода каких либо данных. Все время забываю синтаксис, приходится каждый раз искать. Решил записать в блоге, чтобы уж не терять :). Во всех ...

Читать

 

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