Hay varias maneras de hacer esto. Enumeraré los métodos para aumentar la eficiencia:
Usando la clasificación:
Complejidad de tiempo: O (N * log N)
- ¿Qué algoritmos avanzados usa un sitio como Facebook?
- Cómo resolver este problema SPOJ
- Cómo calcular el orden de crecimiento para un fragmento de código dado
- ¿Qué es el algoritmo k-Nearest Neighbour? ¿Qué tipo de problemas puede resolver este algoritmo? ¿Qué tipo de matemática se requiere?
- ¿Cuáles son todos los diferentes tipos de recursividad en la programación?
Complejidad espacial: O (N)
Algoritmo
Ordene la matriz en orden ascendente (o descendente). Comience desde el primer elemento y compare el elemento actual con el siguiente elemento; si son iguales, imprima este elemento y rompa el ciclo; de lo contrario, continúe este proceso hasta el segundo último elemento.
Implementación de C ++:
#include
usando el espacio de nombres estándar;
int main () {
vector arr (101);
cout << "Lea su matriz:" << endl;
para (auto & i: arr)
cin >> i;
sort (arr.begin (), arr.end ());
para (int i = 0; i <n – 1; ++ i) {
if (arr [i] == arr [i + 1]) {
cout << "Número duplicado =" << arr [i];
devuelve 0;
}
}
cout << "No hay duplicados";
}
2. Utilizando la tabla Hash implementada en matriz:
Complejidad de tiempo: O (N)
Complejidad espacial: 0 (N)
Algoritmo
Cree una matriz auxiliar booleana llamada como cuenta, cuyo elemento se inicializa en falso. Cuente la ocurrencia de todos los elementos. El recuento de un elemento i se almacenará en el recuento [i – 1] (i es un entero de entrada). Si el recuento [i-1] es verdadero, imprima; de lo contrario, asigne el conteo [i-1] a verdadero.
Implementación de C ++:
#include
usando el espacio de nombres estándar;
int main () {
vector cuenta (100, falso);
cout << "Lea su matriz:" << endl;
para (int j = 0; j <101; ++ j) {
int i;
cin >> i;
if (cuenta [i – 1]) {
cout << "Número duplicado =" << i;
devuelve 0;
}
cuenta [i – 1] = verdadero;
}
cout << "No hay duplicados";
}
3. Enfoque más rápido: utilice la operación XOR.
Complejidad de tiempo: O (N)
Complejidad espacial: O (1)
Algoritmo
Tome XOR de todos los números en el rango de 1 a 100. Ahora tome XOR de todos los elementos de la matriz de entrada. El resultado de la variable XORed será la respuesta.
Implementación de C ++:
#include
int main () {
int xor = 1;
para (int i = 2; i <= 100; ++ i)
xor ^ = i;
cout << "Lea su matriz:";
para (int i = 0; i <101; ++ i) {
int temp;
cin >> temp;
xor ^ = temp;
}
si (! xor)
cout << "Número duplicado =" << xor;
más
cout << "No hay duplicados";
}
