tipos - ¿Se puede eliminar el bucle for de este fragmento de código PHP?

tipos de ciclos en programacion

Question

Tengo un rango de números enteros que pueden o no tener algunos números faltantes. ¿Es posible encontrar el número más pequeño que falta sin usar una estructura de bucle? Si no faltan números, la función debe devolver el valor máximo del rango más uno.

Así es como lo resolví usando un bucle 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;
}

Idealmente, me gustaría evitar el bucle completo, ya que el alcance puede ser masivo. ¿Alguna sugerencia?

Answer 1

$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

Answer 2

Algo solución

Hay una forma de verificar si falta un número usando un algoritmo. Se explica aquí . Básicamente, si necesitamos sumar números del 1 al 100. No necesitamos calcular sumando solo tenemos que hacer lo siguiente: (100 * (100 + 1)) / 2 . Entonces, ¿cómo va a resolver esto nuestro problema?

Vamos a obtener el primer elemento de la matriz y el último. Calculamos la suma con este algo. Luego usamos array_sum() para calcular la suma real. Si los resultados son los mismos, no hay ningún número faltante. Entonces podríamos "retroceder" el número que falta al restar la suma real de la calculada. Esto, por supuesto, solo funciona si solo falta un número y fallará si faltan varios. Así que pongamos esto en código:

  $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
    }
  }

Salida

8
3

Demo en línea

Si faltan varios números, simplemente use array_map() o algo similar para hacer un bucle interno.

Solución Regex

Llevemos esto a un nuevo nivel y usemos regex! Sé que no tiene sentido, y no debería usarse en aplicaciones del mundo real. El objetivo es mostrar el verdadero poder de Regex :)

Entonces, primero hagamos una cadena fuera de nuestro rango en el siguiente formato: I,II,III,IIII para el rango 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;

El resultado debería ser algo así como: I,II,III,IIII,IIIII,IIIIII,IIIIIII .

He creado la siguiente expresión regular: ^(?=(I+))(^/1|,/2I|/2I)+$ . Entonces, qué significa esto ?

^                   # 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

Veamos qué está pasando realmente ...

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.

Verlo funcionando y fallando . Y pongámoslo en el código 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 !'';
}

Ahora tomemos en cuenta para devolver el número que falta, eliminaremos el carácter $ end para que nuestra expresión regular no falle, y usaremos el grupo 2 para devolver el número perdido:

$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
}

Demo en línea

Answer 3

echo min(array_diff(range(0, max($range)+1), $range));

Answer 4

Sencillo

$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]; 

Answer 5

Honestamente, no entiendo por qué no querrías usar un bucle. No hay nada de malo con los bucles. Son rápidos, y simplemente no puedes prescindir de ellos. Sin embargo, en su caso, hay una manera de evitar tener que escribir sus propios bucles, utilizando las funciones básicas de PHP. Sin embargo, recorren el conjunto, pero simplemente no puedes evitar eso.
De todos modos, reúno lo que está buscando, se puede escribir fácilmente en 3 líneas:

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

Probado con:

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

Y ahora, robar desvergonzadamente la respuesta de Pé de Leão (pero "aumentarla" para hacer exactamente lo que quieras):

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;
}

Cómo funciona:

$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];

Eso es todo, realmente.
Por supuesto, si la matriz suministrada puede contener valores null o falsy , o incluso cadenas y valores duplicados, podría ser útil "limpiar" un poco la entrada:

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];
}

Enlaces útiles:

• La página de array_diff man array_diff
• Las funciones max y min
• Buena range Ol '', por supuesto ...
• La función array_filter
• La función array_map podría valer la pena mirar
• Así como array_sum podría ser

Answer 6

$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.
}

Answer 7

Técnicamente, no puedes prescindir del loop (a menos que solo quieras saber si falta un número). Sin embargo, puede lograr esto sin primero ordenar la matriz.

El siguiente algoritmo usa el tiempo O (n) con el espacio 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;

Construye un mapa de identidad ordenado de N entradas, marcando cada valor contra su posición como "1"; al final, todas las entradas deben ser "1", y la primera entrada "0" es el valor más pequeño que falta.

Por cierto, estoy usando una cadena temporal en lugar de una matriz para reducir los requisitos de memoria física.

Answer 8

puedes usar array_diff() como este

<?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;

?>

Answer 9

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 ) );

Answer 10

EDITAR NOTA
Esta pregunta es sobre el rendimiento. Las funciones como array_diff y array_filter no son mágicamente rápidas. Pueden agregar una penalización de tiempo enorme . Reemplazar un bucle en tu código con una llamada a array_diff no hará mágicamente las cosas, y probablemente hará las cosas más lentas . Debe comprender cómo funcionan estas funciones si tiene la intención de usarlas para acelerar su código.

Esta respuesta utiliza la suposición de que no hay elementos duplicados y no existen elementos no válidos que nos permitan usar la posición del elemento para inferir su valor esperado.

Esta respuesta es teóricamente la solución más rápida posible si comienza con una lista ordenada . La solución publicada por Jack es teóricamente la más rápida si se requiere clasificación.

En la serie [0,1,2,3,4, ...], el n -ésimo elemento tiene el valor n si no hay elementos antes de que falte. Entonces podemos verificar en cualquier punto para ver si nuestro elemento faltante es anterior o posterior al elemento en cuestión.

Así que empiezas cortando la lista por la mitad y verificando si el artículo en la posición x = x

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

Sí, list[4] == 4 . Así que muévase a mitad de camino de su punto actual al final de la lista.

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

Uh-oh, list[6] == 7 . Entonces, en algún punto entre nuestro último punto de control y el actual, faltaba un elemento. Divida la diferencia a la mitad y verifique ese elemento:

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

En este caso, list[5] == 5

Así que estamos bien allí. Entonces tomamos la mitad de la distancia entre nuestro cheque actual y el último que fue anormal. Y oh ... parece que la celda n+1 es una que ya hemos comprobado. Sabemos que la list[6]==7 y la list[5]==5 , por lo que el elemento número 6 es el que falta.

Como cada paso divide a la mitad el número de elementos a considerar, usted sabe que el peor de los casos no controlará más que el registro ₂ del tamaño total de la lista. Es decir, esta es una solución O (log (n)) .

Si todo este arreglo te parece familiar, es porque lo aprendiste en tu segundo año de universidad en una clase de informática. Es una variación menor en el algoritmo de búsqueda binaria, uno de los esquemas de índice más utilizados en la industria. De hecho, esta pregunta parece ser una aplicación perfectamente diseñada para esta técnica de búsqueda.

Por supuesto, puede repetir la operación para encontrar elementos faltantes adicionales, pero como ya ha probado los valores en los elementos clave de la lista, puede evitar volver a verificar la mayoría de la lista e ir directamente a los más interesantes para probar.

También tenga en cuenta que esta solución asume una lista ordenada. Si la lista no está ordenada, entonces, obviamente, la ordena primero. Excepto que la búsqueda binaria tiene algunas propiedades notables en común con el quicksort. Es muy posible que pueda combinar el proceso de clasificación con el proceso de encontrar el elemento que falta y hacer ambas cosas en una sola operación, ahorrándose algo de tiempo.

Finalmente, para resumir la lista, es solo un estúpido truco de matemáticas arrojado por si acaso. La suma de una lista de números de 1 a N es solo N*(N+1)/2 . Y si ya has determinado que faltan elementos, entonces obviamente resta los elementos faltantes.