0
1.8K
VistasEncuentre el entero positivo más pequeño que no ocurre en una matriz
Estoy probando el siguiente ejercicio para mejorar mis habilidades en línea, se me presentó el siguiente problema.
Esta es una tarea de demostración.
Escribe una función: class Solution { public int solution(int[] A); } que, dada una matriz A de N enteros, devuelve el entero positivo más pequeño (mayor que 0) que no aparece en A.
Por ejemplo,
Dado A = [1, 3, 6, 4, 1, 2], la función debería devolver 5. Dado A = [1, 2, 3], la función debería devolver 4. Dado A = [-1, -3] , la función debería devolver 1.
Escriba un algoritmo eficiente para las siguientes suposiciones: • N es un número entero dentro del rango [1..100,000); • cada elemento de la matriz A es un número entero dentro del rango (-1,000,000.. 1,000,000).
Lo resolví usando la siguiente solución:
<?php class Solution { public function($A) { $posInts = [1, 2, 3, 4, 5, 6, 7, 8, 9]; $diffs = array_diff($postInts, $A); $smallestPosInt = min($diffs); return $smallestPosInt; } } Sin embargo, al enviar obtuve la siguiente puntuación: 
Ahora no estoy muy seguro de lo que hice mal aquí o de cómo puedo reescribir el código con un algoritmo mejor.
3 Respuestas
Responde la pregunta0
Simplemente repetiría (incrementaría) cualquier número entero posible:
function solution($A) { $result = 1; $maxNumber = max($A); for (; $result <= $maxNumber; $result++) { if (!in_array($result, $A)) { break; } } return $result; } var_dump(solution([1, 3, 6, 4, 1, 2])); // int(5) var_dump(solution([1, 2, 3])); // int(4) var_dump(solution([-1, -3])); // int(1) // As a bonus, this also works for larger numbers: var_dump(solution([1, 3, 6, 4, 1, 2, 7, 8, 9, 10, 11, 12, 13, 5, 15])); // int(14)Editar con respecto al rendimiento:
Como se señaló en los comentarios (y usted mismo ya lo dijo), esta no es una solución muy eficiente.
Si bien actualmente no tengo suficiente tiempo disponible para realizar pruebas de rendimiento reales, creo que esto debería estar cerca de una solución O (n): (teniendo en cuenta que no estoy seguro de cómo se implementan las matrices en el lado C de PHP)
function solution($A) { $result = 1; $maxNumber = max($A); $values = array_flip($A); for (; $result <= $maxNumber; $result++) { if (!isset($values[$result])) { break; } } return $result; } // Not posting the output again because it is naturally the same ;)El "truco" aquí es voltear la matriz primero para que los valores se conviertan en índices. Dado que a) no nos importan los índices originales yb) no nos importa si los valores duplicados se sobrescriben entre sí, podemos hacerlo con seguridad.
Usar isset() en lugar de in_array() debería ser mucho más rápido, ya que básicamente solo verifica si existe una variable (en este caso, almacenada en un índice específico de la matriz) y, por lo tanto, PHP no tiene que iterar a través de la matriz para poder compruebe si cada número que recorremos existe o no dentro de él.
PD: Después de pensarlo dos veces, creo que esto aún puede estar más cerca de O (n * 2) porque max() probablemente realiza un bucle para encontrar el valor más alto. También puede eliminar esa línea y compararla con el número más alto que hay en PHP como una salida de emergencia, así: for (; $result <= PHP_INT_MAX; $result++) { ... } como una optimización adicional. O tal vez simplemente codifique el número más alto permitido como se especifica en la tarea.
0
Si se nos permite modificar la entrada, realice esto en su lugar; de lo contrario, cree una nueva matriz de tamaño n + 1:
Para cada elemento encontrado en la matriz original, si es mayor que n + 1 o menor que 1, asigne 0 en el índice del elemento (índice - 1 si se realiza en el lugar); de lo contrario, asigne 1 en el índice de la matriz que es el valor y asigne 0 en su propio índice si es diferente. Después de eso, ejecute un segundo recorrido e informe el primer índice (índice + 1 si se realiza en el lugar) mayor que cero con valor 0 o n + 1.
[1, 3, 6, 4, 1, 2] => [1, 1, 1, 1, 0, 1] report 50
Consulte esta respuesta usando Javascript de una manera que funcione con el mejor rendimiento posible -Si no me equivoco- O (N).
function solution(A) { const set = new Set(A) let i = 1 while (set.has(i)) { i++ } return i }