¿Podría hacerlo sin espacio adicional y en tiempo de ejecución O (n)?

Se puede resolver mis índices de marcado. si algún elemento aparece por primera vez, haga que ese índice sea negativo; de lo contrario, si aparece por segunda vez, no tenemos que hacer nada.

atravesar nuevamente la matriz y si algún valor es positivo, significa que ese valor no existe

estamos usando -1 porque los valores se encuentran entre 1 y n.

vector findDisappearedNumbers (vector & nums) {
vector ans;
para (int i = 0; i {
if (nums [nums [i] -1]> 0)
{
nums [nums [i] -1] = -nums [nums [i] -1];
}
}
para (int i = 0; i {
if (nums [i]> 0)
{
ans.push_back (i + 1);
}
}
volver ans;
}

Use una matriz booleana para realizar un seguimiento de los números que ha encontrado hasta ahora.

Al final, cuente la cantidad de puntos en la matriz que no se alternaron, esa sería su respuesta

Si. Es posible hacer esto en tiempo lineal y espacio constante.

Me gusta llamar a este concepto ‘negación’: es donde el índice de una matriz basada en un valor distinto de cero denota la presencia / ausencia de ese elemento en la matriz.

Un ejemplo: si tenemos 2 en la matriz (arte), el elemento en arr [2] (¡suponiendo que el índice comience en 1!) Se marcará como negativo. Este elemento negativo en arr [2] denota la presencia de un 2 en arr.

Para una redacción exhaustiva, consulte este enlace: encuentre el número positivo más pequeño que falta en una matriz sin clasificar – GeeksforGeeks

¡Espero eso ayude!

Si. Dado un elemento, es posible asignarle un índice de matriz en función de su valor. Esto hace posible ordenar la matriz en una sola pasada. Después de ordenar, quedará con agujeros que no tienen asignado ningún número. Esos índices vacíos le dicen qué valores faltan.

Puede usar un algoritmo de clasificación en el lugar y luego buscar huecos en la secuencia. Si usa quicksort, obtiene O (Nlog N) al menos, pero creo que puede obtener tiempo lineal con una versión modificada de conteo. En cualquier caso, debería ser posible explotar la estructura; enteros casi secuenciales, para hacer un algoritmo de clasificación rápido.

Es realmente malo tratar de conseguir quora para hacer su tarea por usted. Te dan tarea para ayudarte a aprender. Es importante aprender que usted mismo hace la tarea, no que le digan la respuesta.

Haga algo similar a la publicación a continuación. Se discuten tres enfoques:

Encuentra un elemento duplicado en una matriz de rango limitado – Techie Delight