Вот задание: Дан массив произвольного размера с числами в пределах от 1 до 1,000,000. В этом массиве все числа уникальные, кроме одного числа, которое повторяется два раза. Найти это число. Решить эту задачу с минимальным использованием процессорного времени. Решить на PHP. Как решил я: PHP: function find_duplicate($array) { $arrTemp = array(); foreach ($array as $v) { if (isset($arrTemp[$v])) { return $v; } $arrTemp[$v] = true; } return null; } $arr1 = array(100,2,5,11,180,0,45,6,87,2000,77,100); echo 'Duplicates found: '. find_duplicate($arr1); Результат проверки: решено верно, но не оптимально – используется прямой перебор массива Вопрос: Как можно решить эту задачу ещё оптимальнее? Что за "не прямой" перебор массива?
https://php.ru/manual/function.array-unique.html --- Добавлено --- в гугл достаточно забить было пхп функция дубликат значений
PHP: : function find_duplicate($array) { $arrTemp = array(); foreach (array_count_values($array) as $k => $v) { if ($v > 1) $arrTemp[] = $k; } return $arrTemp; } $arr1 = array(100,2,5,11,180,0,45,6,87,2000,77,100); echo 'Duplicates found: '; print_r(find_duplicate($arr1));
Тут, конкретно под задачу(при соблюдении условий задачи), двух функций хватает. PHP: $arr1 = array(100,2,5,11,180,0,45,6,87,2000,77,100); echo array_search(2,array_count_values($arr1));
PHP: $array_1 = array(100,2,5,11,180,0,45,6,87,2000,77,100); $array_2 = array_unique($array_1); $a = array_diff_assoc($array_1, $array_2); var_dump($a); перебор все равно произойдет, какая разница что он будет скрыт в дебрях C
Генерация массива PHP: $arr = []; $i = 999999; while ($i--) { $arr[] = (int) ($i * pi()); if ($i === 323765) { $arr[] = (int) ($i * pi()); } } дублирующееся число: 1017137 Функция @IvanRsn Код (Text): 0.296 сек 0.328 сек 0.299 сек 0.254 сек 0.306 сек Функция @Zuldek Код (Text): 0.239 сек 0.285 сек 0.241 сек 0.237 сек 0.245 сек Способ @mahmuzar Код (Text): 0.109 сек 0.101 сек 0.103 сек 0.098 сек 0.103 сек Способ @storms89 Код (Text): 3.251 сек 3.115 сек 3.063 сек 3.345 сек 3.302 сек Моя функция PHP: function find_duplicate($array) { return array_sum($array) - array_sum(array_keys(array_flip($array))); } Код (Text): 0.105 сек. 0.118 сек. 0.123 сек. 0.115 сек. 0.109 сек.
PHP: function find_duplicate($array) { return array_sum($array) - array_sum(array_keys(array_flip($array))); } $a = find_duplicate(array(100,2,5,11,180,0,45,6,87,2000,2000,77,100)); var_dump($a); == 2100, WTF? при прочем, функция Zuldek, также как и array_diff находит больше чем 1 дубликат
тогда можно и так, не? PHP: function find_duplicate_in_array_with_one_duplicate(&$arr) { return array_flip(array_count_values($arr))[2]; } $start = microtime(true); var_dump(find_duplicate_in_array_with_one_duplicate($arr)); echo "\n".microtime(true) - $start; //0.051091194152832 with php 7+
@storms89 можно, результат на моем хосте Код (Text): 0.139 сек 0.117 сек 0.113 сек 0.114 сек 0.114 сек PHP 7.1.3
назначение длинных наименований функций и переменных замедляет быстродействие компилятора пхп --- Добавлено --- не помню точно предел символов 25 вроде
Вероятно, самый правильный вариант этот https://php.ru/forum/threads/algoritmy-poleznosti.54173/page-2#post-525858 Т.к. находит все дубликаты.
Эта "оптимизация" умерла еще раньше, чем mysql_ стал deprecated же. Плюс opCache ныне - часть дистриба PHP. И он работает отлично. И ты хоть войну и мир в качестве названия переменной используй.