Tarea de prueba en C – aparentemente mi solución no supera algunos casos de prueba.
Actualmente estoy tratando de practicar mis habilidades en C en algunas tareas de prueba de demostración. Me encontré con la siguiente tarea e implementé una solución que no pasa la prueba. ¿Puedes revisar mi solución y señalar qué casos he pasado por alto alternativamente cómo podría hacer la solución más eficiente? ¡Básicamente cualquier entrada es apreciada!
Tarea:
Escribe una función:
int solution(int A[], int N);
que, dado un array 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.
Escribe un algoritmo eficiente para las siguientes suposiciones: N es un entero dentro del rango [1..100,000]; cada elemento del array A es un entero dentro del rango [-1,000,000..1,000,000].
Mi solución:
int solution(int A[], int N) {
int B[N];
unsigned int Bidx=0;
unsigned int i = 0;
int smallest = 1000000;
// deshacerse de los elementos negativos y encontrar el elemento positivo más pequeño
for(i=0; i<;N; i++)
{
if(A[i]>0)
{
B[Bidx]=A[i];
Bidx++;
if(A[i] < smallest)
smallest = A[i];
}
}
// si no se encuentran elementos positivos, la solución es 1
if(Bidx == 0)
return 1;
// iterar a través de los valores positivos para encontrar el valor no presente más pequeño
int condition = 1;
int candidate = smallest+1;
while(condition)
{
condition = 0;
for(i=0; i < Bidx; i++)
{
if(B[i] == candidate)
{
candidate++;
condition = 1;
}
}
}
return candidate;
}
davy.ai
Tu solución es correcta para la mayoría de los casos, pero hay algunos casos extremos que tu solución no cubre, que son los siguientes:
Para solucionar estos problemas, puedes modificar tu solución de la siguiente manera:
Aquí tienes el código actualizado:
Esta solución debería ser más eficiente y cubrir todos los casos extremos.