Si el tamaño de una matriz es 101 y el rango de números es de 0 a 99, solo un número viene 2 veces. ¿Cuál es ese número?

Pregunta: Hay una matriz de tamaño 101 en la que hay números del 0 al 99 completos y solo existe un par de cualquier número entre 0 y 99. ¿Cuál es ese número duplicado?

Hay muchas formas de resolver este problema. Analicemos uno por uno con la complejidad del tiempo también.

Usando la fórmula de suma de números naturales.
Simplemente encuentre la suma de los números naturales del 0 al 99, es decir, n (n + 1) / 2.
Esto nos da 99 * 100/2 = 4950.
Ahora la diferencia absoluta de 4950 y la suma de los elementos de la matriz nos dará el número duplicado.
Complejidad de tiempo: O (n)
Usando la clasificación
Ordenar nuestra matriz traerá nuestros elementos duplicados adyacentes entre sí. Con esto en mente, podemos atravesar la matriz y encontrar cualquier duplicado comparando los elementos en la matriz con sus adyacentes. Si descubriste que son iguales, tienes tu respuesta.
Complejidad de tiempo: O (nlgn)
Nota: También puede aplicar algoritmos de ordenación de tiempo lineal aquí ya que los datos están en límites fijos y, por lo tanto, logran una complejidad de O (n).
Hashing
También podemos usar hashing para resolver este problema. Mientras recorremos la matriz, mantendremos un HashSet que almacenará todos los números vistos antes de un elemento particular que estamos viendo en nuestro recorrido. Entonces, si en nuestra iteración alcanzamos un número x y descubrimos que también se mantiene en HashSet, eso significa que encontramos ese número x antes, por lo tanto, obtuvimos nuestra respuesta.
Complejidad del tiempo: O (n).

Puede haber muchas más formas de resolver esta pregunta, pero estas son solo algunas.

¡Feliz codificación! 🙂

AlgoritmosnúmerosProgramación informática

Cómo reducir la programación dinámica a programación lineal

Cómo determinar todas las condiciones, suposiciones y limitaciones para un código C # dado que calcula el valor promedio de una matriz de diferentes números

¿Son los sentimientos la función del costo del algoritmo de aprendizaje automático de los humanos?

Cómo escribir una función recursiva usando Python que toma una cadena como entrada e imprime cada carácter en una línea separada

Si F2L se resuelve mejor de forma intuitiva, ¿por qué cada tutorial incluye algoritmos para todos los casos de F2L?

¿Por qué recibo un error de tiempo de ejecución en la conversión de un árbol binario a un árbol binario enhebrado?

Agregue todos los números del 0 al 99 y almacene en una variable, diga Suma (use la fórmula AP para esto, Sn = n * (n + 1) / 2)
atravesar cada elemento del primero al último índice
restar cada elemento atravesado de la suma
Al final tendremos el número (en negativo)

Esto se puede implementar fácilmente

Gracias, para más programación visite

Debadatta Meher

Si puedo replantear la pregunta: hay una matriz cuyo tamaño es 101 y los números del 0 al 99 están completos y solo existe un duplicado de cualquier número entre 0 y 99. ¿Cuál es el número duplicado?

Esto se puede resolver utilizando nuestras matemáticas de secundaria.

Suma de n números consecutivos

n (n + 1) / 2

En este caso 99 * 100/2 = 4950. Ahora recorra la matriz para encontrar la suma de elementos.

Resta ambos resultados y encontrarás el duplicado.

Espero que este enfoque ayude. Cualquier sugerencia o comentario bienvenido.

Debadatta Meher

Según el tamaño mencionado para la matriz, hay 101 elementos en ella.

Según el rango de números mencionados que están contenidos en la matriz, {0–99} es decir, un total de 100 elementos.

Ahora, la suma de n números naturales =

[matemáticas] (n * (n + 1)) / 2 [/ matemáticas]

Aquí, n = 99