Оказывается, очень частая задача в тестовых заданиях соискателей — это поиск дубля в массиве. В зависимости от нюансов конкретного задания, могут просить:
- найти все дубли или один единственный дубль;
- использовать в решении самый быстрый алгоритм;
- найти вообще все повторяющиеся варианты.
Я рассмотрю здесь частное решение (целых три варианта), которое вы подкрутите для своего случая. Это поиск единственного дубля в массиве чисел.
Итак, пусть $A — произвольный массив чисел. Напишем функцию, которая ищет близнеца или возвращает FALSE.
Скоростной вариант
Самый первый и самый быстрый вариант поиска — это положиться только на функции PHP без каких либо свои циклов и ветвлений.
|
1 2 3 4 |
function array_find_twins($A) { $N = array_flip(array_count_values($A)); return isset($N[2]) ? $N[2] : FALSE; } |
Мы посчитали число значений, а потом просто вывернули массив. Если дублей было несколько — останется только один. Если нужно другое число повторений — используйте другой ключ на выходе (не 2, а 3, 4..).
PHP гораздо быстрее работает внутри собственных откомпилированных функций, нежели с вашими алгоритмами, какими бы они не были гениальными.
Вариант с сортировкой
Здесь мы сортируем массив, чтобы потом «вручную» просканировать его и найти рядом стоящих близнецов.
Так мы обнаружим любое повторяющееся произвольное число раз значение (т.е. тройняшек, и т.д.)
|
1 2 3 4 5 6 7 8 9 10 11 |
function array_find_twins2($A) { sort($A, SORT_NUMERIC); $last = -1; foreach($A as $value) { if ($last == $value) { return $value; } $last = $value; } return FALSE; } |
Если по условиям задачи массив уже отсортирован, то sort() можно убрать. Останется сканер массива, быстродействие которого линейно зависит от размеров массива.
В среднем, этот вариант в 2-3 раза медленнее предыдущего (на диапазоне от 1к до 100 к элементов).
Перекладываем из одной корзины в другую
Самый тормозной, неэффективный из трех.
Мы перебираем вх. массив ($A), складывая элементы в другой ($B). Но если в нем ($B) уже есть искомое значение, то вуаля! мы нашли близнеца.
|
1 2 3 4 5 6 7 8 9 |
function array_find_twins3($A) { $B = array(); $last = -1; foreach($A as $value) { if (in_array($value, $B)) return $value; $B[] = $value; } return FALSE; } |
В некоторых случаях, такая конструкция бывает востребована. Например, когда вы должны провести какие вычисления с каждым элементом, а потом уже принимать решение об эквивалентности.
Этот вариант на 2 порядка хуже первого решения.
Если у вас есть другие варианты — присылайте :).
