Si tenemos una matriz de todos los números hasta N (N < 10), ¿cuál es la mejor manera de encontrar todos los números que faltan? Ejemplo:Encuentra los números que faltan
N = 5
1 5 3 2 3
Output: 1 5 4 2 3
En el ex, el número 4 fue la falta y había 2 3s, por lo que sustituye la primera con 4 y ahora la matriz es completa - todos los números de hasta 5 están allí .
¿Hay algún algoritmo simple que pueda hacer esto?
Puede usar un set data structure - uno para todos los números hasta N, uno para los números que realmente vio y usar una diferencia establecida.
Innecesariamente use un algoritmo O (N log N) donde O (N) es suficiente. – kennytm
Bueno, ValoisBorn dijo un algoritmo simple. La suya es mejor; pero es simple? –
Creo que (uno de) los algoritmos O (N) es más simple que realmente entender cómo funciona un conjunto. Es más fácil simplemente usar un conjunto, pero no llegarás lejos usando cosas que no entiendes ... – IVlad
Una forma de hacerlo sería observar cada elemento de la matriz en secuencia, y ver si ese elemento ya se ha visto antes en elementos que ya ha comprobado. Si es así, cambie ese número por uno que no haya visto antes y proceda.
Permítanme presentarles a mi amigo Schlemiel the Painter. El descubrimiento de un método más eficiente se deja como un desafío para el lector.
Este tipo de tarea se ve como tarea, por favor, háganos saber si no lo es. Te daré una pequeña sugerencia, y luego mejoraré mi respuesta si confirmas que esto no es tarea.
Mi consejo por ahora es este: si tuviera que hacer esto a mano, ¿cómo lo haría? ¿Escribirías una lista extra de números de algún tiempo, leerías la lista (¿cuántas veces?)? etc.
Para problemas simples, algunas veces modelar su algoritmo después de un enfoque intuitivo con las manos puede funcionar bien.
asume todos los números dentro del rango de 1 x ≤ ≤ N.
Mantenga 2 arrays de tamaño output N., used (como una matriz asociativa). Inicializar todos ellos a 0.
Scan desde la derecha , rellenar los valores a menos que sea outputused.
Compruebe los valores no utilizados y colóquelos en las ranuras vacías (cero) de output en ese orden.
O (N) complejidad del tiempo, O (N) complejidad del espacio.
Como N es muy pequeño, puede usar F [i] = k si el número i aparece k veces.
int F[10]; // make sure to initialize it to 0
for (int i = 0; i < N; ++i)
++F[ numbers[i] ];
Ahora, para reemplazar los duplicados, atraviesan la matriz de número y si el número actual aparece más de una vez, su recuento de decremento y reemplazarlo con un número que aparece 0 veces y incrementa el contador de ese número. Puede mantener esta O (N) si mantiene una lista de números que no aparecen en absoluto. Dejaré que descubras qué se debe hacer exactamente, ya que esto suena como tarea.
+1 estuvo a punto de responder el mismo. –
Aquí hay un enlace que leí hoy que puede ser útil. http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html
Debe especificar el problema más claramente. ¿Cómo se hizo el reemplazo? Digamos que sé que falta un número. ¿Dónde lo pongo en la matriz?¿Por qué eligió reemplazar el primer '3' por' 4' (en comparación con el último '3')? ¿Sería correcto si reemplazaras el último '3' con' 4' en su lugar? – AnT
Ayudaría, si se responde la pregunta de Andrey. – Jagannath