За последние 24 часа нас посетили 18774 программиста и 1608 роботов. Сейчас ищут 665 программистов ...

Не прямой перебор массива (задача с собеседования).

Тема в разделе "PHP для профи", создана пользователем IvanRsn, 7 июн 2017.

  1. IvanRsn

    IvanRsn Новичок

    С нами с:
    4 июн 2017
    Сообщения:
    5
    Симпатии:
    0
    Вот задание:
    Дан массив произвольного размера с числами в пределах от 1 до 1,000,000. В этом массиве все числа уникальные, кроме одного числа, которое повторяется два раза. Найти это число. Решить эту задачу с минимальным использованием процессорного времени. Решить на PHP.

    Как решил я:
    PHP:
    1. function find_duplicate($array) {
    2.     $arrTemp = array();
    3.     foreach ($array as $v) {
    4.         if (isset($arrTemp[$v])) {
    5.             return $v;
    6.         }
    7.         $arrTemp[$v] = true;
    8.     }
    9.     return null;
    10. }
    11.  
    12. $arr1 = array(100,2,5,11,180,0,45,6,87,2000,77,100);
    13. echo 'Duplicates found: '. find_duplicate($arr1);
    Результат проверки:
    решено верно, но не оптимально – используется прямой перебор массива

    Вопрос: Как можно решить эту задачу ещё оптимальнее? Что за "не прямой" перебор массива?
     
  2. MouseZver

    MouseZver Суперстар

    С нами с:
    1 апр 2013
    Сообщения:
    7.788
    Симпатии:
    1.328
    Адрес:
    Лень
  3. Zuldek

    Zuldek Старожил

    С нами с:
    13 май 2014
    Сообщения:
    2.381
    Симпатии:
    344
    Адрес:
    Лондон, Тисовая улица, дом 4, чулан под лестницей
    PHP:
    1. :
    2. function find_duplicate($array) {
    3.   $arrTemp = array();
    4.   foreach (array_count_values($array) as $k => $v) {
    5.   if ($v > 1) $arrTemp[] = $k;
    6.   }
    7.   return $arrTemp;
    8. }
    9. $arr1 = array(100,2,5,11,180,0,45,6,87,2000,77,100);
    10. echo 'Duplicates found: ';
    11. print_r(find_duplicate($arr1));
     
  4. mahmuzar

    mahmuzar Старожил

    С нами с:
    6 апр 2012
    Сообщения:
    4.631
    Симпатии:
    425
    Адрес:
    РД, г. Махачкала.
    Тут, конкретно под задачу(при соблюдении условий задачи), двух функций хватает.
    PHP:
    1. $arr1 = array(100,2,5,11,180,0,45,6,87,2000,77,100);
    2.  
     
    IvanRsn, TeslaFeo, artoodetoo и ещё 1-му нравится это.
  5. Zuldek

    Zuldek Старожил

    С нами с:
    13 май 2014
    Сообщения:
    2.381
    Симпатии:
    344
    Адрес:
    Лондон, Тисовая улица, дом 4, чулан под лестницей
    верно, если не вдаваться в спички
     
  6. storms89

    storms89 Активный пользователь

    С нами с:
    20 июн 2016
    Сообщения:
    59
    Симпатии:
    10
    PHP:
    1. $array_1 = array(100,2,5,11,180,0,45,6,87,2000,77,100);
    2. $array_2 = array_unique($array_1);
    3. $a = array_diff_assoc($array_1, $array_2);
    перебор все равно произойдет, какая разница что он будет скрыт в дебрях C
     
  7. [vs]

    [vs] Суперстар
    Команда форума Модератор

    С нами с:
    27 сен 2007
    Сообщения:
    10.557
    Симпатии:
    631
    Генерация массива
    PHP:
    1. $arr = [];
    2. $i = 999999;
    3. while ($i--) {
    4.   $arr[] = (int) ($i * pi());
    5.   if ($i === 323765) {
    6.     $arr[] = (int) ($i * pi());
    7.   }
    8. }
    дублирующееся число: 1017137

    Функция @IvanRsn
    Код (Text):
    1. 0.296 сек
    2. 0.328 сек
    3. 0.299 сек
    4. 0.254 сек
    5. 0.306 сек
    Функция @Zuldek
    Код (Text):
    1. 0.239 сек
    2. 0.285 сек
    3. 0.241 сек
    4. 0.237 сек
    5. 0.245 сек
    Способ @mahmuzar
    Код (Text):
    1. 0.109 сек
    2. 0.101 сек
    3. 0.103 сек
    4. 0.098 сек
    5. 0.103 сек
    Способ @storms89
    Код (Text):
    1. 3.251 сек
    2. 3.115 сек
    3. 3.063 сек
    4. 3.345 сек
    5. 3.302 сек
    Моя функция
    PHP:
    1. function find_duplicate($array) {
    2.   return array_sum($array) - array_sum(array_keys(array_flip($array)));
    3. }
    Код (Text):
    1. 0.105 сек.
    2. 0.118 сек.
    3. 0.123 сек.
    4. 0.115 сек.
    5. 0.109 сек.
     
  8. storms89

    storms89 Активный пользователь

    С нами с:
    20 июн 2016
    Сообщения:
    59
    Симпатии:
    10
    PHP:
    1. function find_duplicate($array) {
    2.   return array_sum($array) - array_sum(array_keys(array_flip($array)));
    3. }
    4.  
    5. $a = find_duplicate(array(100,2,5,11,180,0,45,6,87,2000,2000,77,100));
    == 2100, WTF?

    при прочем, функция Zuldek, также как и array_diff находит больше чем 1 дубликат
     
  9. [vs]

    [vs] Суперстар
    Команда форума Модератор

    С нами с:
    27 сен 2007
    Сообщения:
    10.557
    Симпатии:
    631
    @storms89 потому, что в массиве
    два дубликата
     
  10. storms89

    storms89 Активный пользователь

    С нами с:
    20 июн 2016
    Сообщения:
    59
    Симпатии:
    10
    тогда можно и так, не?
    PHP:
    1. function find_duplicate_in_array_with_one_duplicate(&$arr)
    2. {
    3.   return array_flip(array_count_values($arr))[2];
    4. }
    5. $start = microtime(true);
    6. var_dump(find_duplicate_in_array_with_one_duplicate($arr));
    7. echo "\n".microtime(true) - $start; //0.051091194152832  with php 7+
     
  11. [vs]

    [vs] Суперстар
    Команда форума Модератор

    С нами с:
    27 сен 2007
    Сообщения:
    10.557
    Симпатии:
    631
    @storms89 можно, результат на моем хосте
    Код (Text):
    1. 0.139 сек
    2. 0.117 сек
    3. 0.113 сек
    4. 0.114 сек
    5. 0.114 сек
    PHP 7.1.3
     
  12. storms89

    storms89 Активный пользователь

    С нами с:
    20 июн 2016
    Сообщения:
    59
    Симпатии:
    10
    а я на sandbox.onlinephpfunctions.com смотрел, а то хостинга нету
     
  13. MouseZver

    MouseZver Суперстар

    С нами с:
    1 апр 2013
    Сообщения:
    7.788
    Симпатии:
    1.328
    Адрес:
    Лень
    назначение длинных наименований функций и переменных замедляет быстродействие компилятора пхп
    --- Добавлено ---
    не помню точно предел символов 25 вроде
     
  14. storms89

    storms89 Активный пользователь

    С нами с:
    20 июн 2016
    Сообщения:
    59
    Симпатии:
    10
    ага) как и инкапсуляция некого кода в функцию.
    а вообще сейчас у всех аксселераторы
     
  15. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
  16. [vs]

    [vs] Суперстар
    Команда форума Модератор

    С нами с:
    27 сен 2007
    Сообщения:
    10.557
    Симпатии:
    631
    @Chushkin там по задаче один дубль, хотя алгоритм хороший
     
  17. Dilon

    Dilon Активный пользователь

    С нами с:
    4 май 2014
    Сообщения:
    119
    Симпатии:
    4
    Адрес:
    соседний двор
    Хм! Интересно тут оказывается. В первый раз захожу в этот раздел.
     
  18. Fell-x27

    Fell-x27 Суперстар
    Команда форума Модератор

    С нами с:
    25 июл 2013
    Сообщения:
    12.156
    Симпатии:
    1.770
    Адрес:
    :сердА
    Эта "оптимизация" умерла еще раньше, чем mysql_ стал deprecated же. Плюс opCache ныне - часть дистриба PHP. И он работает отлично. И ты хоть войну и мир в качестве названия переменной используй.
     
    denis01 нравится это.