Можно ли исключить цикл for из этого фрагмента кода PHP?

У меня есть целый ряд целых чисел, которые могут или не могут пропустить некоторые числа. Можно ли найти наименьшее пропущенное число без использования структуры цикла? Если пропущенных чисел нет, функция должна вернуть максимальное значение диапазона плюс единицу.

Вот как я решил это с помощью for цикл:

$range = [0,1,2,3,4,6,7];

// sort just in case the range is not in order
asort($range);
$range = array_values($range);

$first = true;
for ($x = 0; $x < count($range); $x++)
{
    // don't check the first element
    if ( ! $first )
    {
        if ( $range[$x - 1] + 1 !== $range[$x])
        {
            echo $range[$x - 1] + 1;
            break;
        }
    }

    // if we're on the last element, there are no missing numbers
    if ($x + 1 === count($range))
    {
        echo $range[$x] + 1;
    }
    $first = false;
}

В идеале я бы хотел полностью избежать зацикливания, поскольку диапазон может быть огромным. Какие-либо предложения?

Источник

10 ответов

Решение

РЕДАКТИРОВАТЬ: ПРИМЕЧАНИЕ
Этот вопрос о производительности. Функции как array_diff а также array_filter не волшебны быстро. Они могут добавить огромный штраф времени. Замена цикла в вашем коде вызовом array_diff волшебным образом не сделает вещи быстрыми, и , вероятно, сделает вещи медленнее. Вы должны понимать, как работают эти функции, если вы собираетесь использовать их для ускорения вашего кода.

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

Этот ответ теоретически является самым быстрым из возможных решений, если вы начнете с отсортированного списка. Решение, опубликованное Джеком, теоретически является самым быстрым, если требуется сортировка.

В серии [0,1,2,3,4,...] n-й элемент имеет значение n, если до него не было ни одного элемента. Таким образом, мы можем провести выборочную проверку в любой момент, чтобы увидеть, находится ли наш отсутствующий элемент до или после рассматриваемого элемента.

Итак, вы начинаете с того, что разрезаете список пополам и проверяете, находится ли элемент в позиции x = x

[ 0 | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 ]
                  ^

Ага, list[4] == 4, Поэтому переместитесь на полпути от текущей точки к концу списка.

[ 0 | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 ]
                          ^

Ой-ой, list[6] == 7, Так что где-то между нашей последней контрольной точкой и текущей, один элемент отсутствовал. Разделите разницу пополам и проверьте этот элемент:

[ 0 | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 ]
                      ^

В этом случае, list[5] == 5

Так что у нас все хорошо. Таким образом, мы берем половину расстояния между нашей текущей проверкой и последней, которая была ненормальной. И о.. это похоже на клетку n+1 это тот, который мы уже проверили. Мы знаем это list[6]==7 а также list[5]==5, так что элемент номер 6 это тот, который отсутствует.

Поскольку каждый шаг делит количество элементов для рассмотрения пополам, вы знаете, что ваша производительность в худшем случае будет проверять не более log2 от общего размера списка. То есть это решение O(log(n)).

Если все это выглядит знакомо, это потому, что вы выучили его еще на втором курсе колледжа на уроке информатики. Это незначительная вариация алгоритма бинарного поиска - одна из наиболее широко используемых схем индексации в отрасли. Действительно, этот вопрос, кажется, идеально продуманное приложение для этой техники поиска.

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

Также обратите внимание, что это решение предполагает отсортированный список. Если список не отсортирован, то, очевидно, вы сначала сортируете его. Кроме того, бинарный поиск имеет некоторые общие свойства с быстрой сортировкой. Вполне возможно, что вы можете объединить процесс сортировки с процессом поиска пропущенного элемента и выполнить оба действия за одну операцию, сэкономив некоторое время.

Наконец, чтобы подвести итог списка, это просто глупый математический трюк для хорошей меры. Сумма списка чисел от 1 до N просто N*(N+1)/2, И если вы уже определили, что какие-либо элементы отсутствуют, то просто вычтите недостающие элементы.

Источник

Алго решение

Есть способ проверить, есть ли пропущенное число, используя алгоритм. Это объясняется здесь. В основном, если нам нужно добавить числа от 1 до 100. Нам не нужно вычислять, суммируя их, мы просто должны сделать следующее: (100 * (100 + 1)) / 2, Так как же это решит нашу проблему?

Мы собираемся получить первый элемент массива и последний. Мы рассчитываем сумму с этим алгоритмом. Затем мы используем array_sum() рассчитать фактическую сумму. Если результаты совпадают, то пропущенный номер отсутствует. Затем мы можем "вернуть" недостающее число, вычтя действительную сумму из рассчитанной. Это, конечно, работает только в том случае, если отсутствует только один номер, и не работает, если пропущено несколько. Итак, давайте поместим это в код:

  $range = range(0,7);  // Creating an array
  echo check($range) . "\r\n"; // check
  unset($range[3]); // unset offset 3
  echo check($range); // check

  function check($array){
    if($array[0] == 0){
      unset($array[0]); // get ride of the zero
    }
    sort($array); // sorting
    $first = reset($array); // get the first value
    $last = end($array); // get the last value
    $sum = ($last * ($first + $last)) / 2; // the algo
    $actual_sum = array_sum($array); // the actual sum
    if($sum == $actual_sum){
      return $last + 1; // no missing number
    }else{
      return $sum - $actual_sum; // missing number
    }
  }

Выход

8
3

Онлайн демо

Если пропущено несколько номеров, просто используйте array_map() или что-то подобное, чтобы сделать внутренний цикл.

Regex решение

Давайте возьмем это на новый уровень и используем регулярные выражения! Я знаю, что это чепуха, и она не должна использоваться в реальных приложениях. Цель - показать истинную силу регулярных выражений:)

Итак, сначала давайте сделаем строку из нашего диапазона в следующем формате: I,II,III,IIII для диапазона 1,3,

$range = range(0,7);
if($range[0] === 0){ // get ride of 0
  unset($range[0]);
}

$str = implode(',', array_map(function($val){return str_repeat('I', $val);}, $range));
echo $str;

Вывод должен быть примерно таким: I,II,III,IIII,IIIII,IIIIII,IIIIIII,

Я придумал следующее регулярное выражение: ^(?=(I+))(^\1|,\2I|\2I)+$, Так что это значит?

^                   # match begin of string
(?=                 # positive lookahead, we use this to not "eat" the match
    (I+)            # match I one or more times and put it in group 1
)                   # end of lookahead
(                   # start matching group 2
    ^\1             # match begin of string followed by what's matched in group 1
        |           # or
    ,\2I            # match a comma, with what's matched in group 2 (recursive !) and an I
        |           # or
    \2I             # match what's matched in group 2 and an I
)+                  # repeat one or more times
$                   # match end of line

Посмотрим, что на самом деле происходит....

I,II,III,IIII,IIIII,IIIIII,IIIIIII
^
(I+) do not eat but match I and put it in group 1

I,II,III,IIII,IIIII,IIIIII,IIIIIII
^
^\1 match what was matched in group 1, which means I gets matched

I,II,III,IIII,IIIII,IIIIII,IIIIIII
 ^^^ ,\2I match what was matched in group 1 (one I in thise case) and add an I to it

I,II,III,IIII,IIIII,IIIIII,IIIIIII
    ^^^^ \2I match what was matched previously in group 2 (,II in this case) and add an I to it

I,II,III,IIII,IIIII,IIIIII,IIIIIII
        ^^^^^ \2I match what was matched previously in group 2 (,III in this case) and add an I to it

We're moving forward since there is a + sign which means match one or more times,
this is actually a recursive regex.
We put the $ to make sure it's the end of string
If the number of I's don't correspond, then the regex will fail.

Видеть это работает и терпит неудачу. И давайте поместим это в код PHP:

$range = range(0,7);
if($range[0] === 0){
  unset($range[0]);
}

$str = implode(',', array_map(function($val){return str_repeat('I', $val);}, $range));
if(preg_match('#^(?=(I*))(^\1|,\2I|\2I)+$#', $str)){
  echo 'works !';
}else{
  echo 'fails !';
}

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

$range = range(0,7);
if($range[0] === 0){
  unset($range[0]);
}
unset($range[2]); // remove 2

$str = implode(',', array_map(function($val){return str_repeat('I', $val);}, $range));
preg_match('#^(?=(I*))(^\1|,\2I|\2I)+#', $str, $m); // REGEEEEEX !!!

$n = strlen($m[2]); //get the length ie the number
$sum = array_sum($range); // array sum

if($n == $sum){
  echo $n + 1; // no missing number
}else{
  echo $n - 1; // missing number
}

Онлайн демо

Источник

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

Следующий алгоритм использует время O(n) с пробелом O(n):

$range = [0, 1, 2, 3, 4, 6, 7];

$N = count($range);
$temp = str_repeat('0', $N); // assume all values are out of place

foreach ($range as $value) {
    if ($value < $N) {
        $temp[$value] = 1; // value is in the right place
    }
}

// count number of leading ones
echo strspn($temp, '1'), PHP_EOL;

Он строит упорядоченную карту идентичности из N записей, помечая каждое значение относительно его позиции как "1"; в конце все записи должны быть "1", а первая запись "0" - это наименьшее пропущенное значение.

Кстати, я использую временную строку вместо массива, чтобы уменьшить требования к физической памяти.

Источник

Я, честно говоря, не понимаю, почему вы не хотите использовать цикл. Там нет ничего плохого с петлями. Они быстрые, и вы просто не можете обойтись без них. Однако в вашем случае есть способ избежать написания собственных циклов, используя основные функции PHP. Они делают цикл по массиву, но вы просто не можете этого избежать.
Во всяком случае, я собираю то, что вы после, можно легко написать в 3 строки:

function highestPlus(array $in)
{
    $compare = range(min($in), max($in));
    $diff = array_diff($compare, $in);
    return empty($diff) ? max($in) +1 : $diff[0];
}

Протестировано с:

echo highestPlus(range(0,11));//echoes 12
$arr = array(9,3,4,1,2,5);
echo highestPlus($arr);//echoes 6

А теперь, чтобы бесстыдно украсть ответ Пе де Леана (но "увеличить" его, чтобы сделать именно то, что вы хотите):

function highestPlus(array $range)
{//an unreadable one-liner... horrid, so don't, but know that you can...
     return min(array_diff(range(0, max($range)+1), $range)) ?: max($range) +1;
}

Как это устроено:

$compare = range(min($in), max($in));//range(lowest value in array, highest value in array)
$diff = array_diff($compare, $in);//get all values present in $compare, that aren't in $in
return empty($diff) ? max($in) +1 : $diff[0];
//-------------------------------------------------
// read as:
if (empty($diff))
{//every number in min-max range was found in $in, return highest value +1
    return max($in) + 1;
}
//there were numbers in min-max range, not present in $in, return first missing number:
return $diff[0];

Это действительно так.
Конечно, если предоставленный массив может содержать null или же falsy значения, или даже строки, и дубликаты значений, может быть полезно немного "очистить" ввод:

function highestPlus(array $in)
{
    $clean = array_filter(
        $in,
        'is_numeric'//or even is_int
    );
    $compare = range(min($clean), max($clean));
    $diff = array_diff($compare, $clean);//duplicates aren't an issue here
    return empty($diff) ? max($clean) + 1; $diff[0];
}

Полезные ссылки:

  • array_diff справочная страница
  • max а также min функции
  • Добрый ол range, конечно...
  • array_filter функция
  • array_map функция может стоить посмотреть
  • Как только array_sum возможно
Источник 
$range = array(0,1,2,3,4,6,7);    
// sort just in case the range is not in order
asort($range);
$range = array_values($range);
$indexes = array_keys($range);
$diff = array_diff($indexes,$range);

echo $diff[0]; // >> will print: 5 
// if $diff is an empty array - you can print 
// the "maximum value of the range plus one": $range[count($range)-1]+1
Источник

Ты можешь использовать array_diff() как это

<?php
        $range = array("0","1","2","3","4","6","7","9");
        asort($range);

    $len=count($range);
    if($range[$len-1]==$len-1){
      $r=$range[$len-1];
   }
    else{
    $ref= range(0,$len-1);
    $result = array_diff($ref,$range);
    $r=implode($result);
}
echo $r;

?>
Источник 
function missing( $v ) {
    static $p = -1;
    $d = $v - $p - 1;
    $p = $v;
    return $d?1:0;
}

$result = array_search( 1, array_map( "missing", $ARRAY_TO_TEST ) );
Источник 
$range = array(0,1,2,3,4,6,7);

$max=max($range);

$expected_total=($max*($max+1))/2; // sum if no number was missing.

$actual_total=array_sum($range);  // sum of the input array.

if($expected_total==$actual_total){
   echo $max+1;      // no difference so no missing number, then echo 1+ missing number.
}else{
   echo $expected_total-$actual_total; // the difference will be the missing number.
}
Источник 
echo min(array_diff(range(0, max($range)+1), $range));
Источник

Просто

$array1 = array(0,1,2,3,4,5,6,7);// array with actual number series
$array2 = array(0,1,2,4,6,7); // array with your custom number series
$missing = array_diff($array1,$array2);
sort($missing);
echo $missing[0];
Источник
Другие вопросы по тегам