Supongo que el título podría ser un poco engañoso, pero no podría pensar en uno mejor. Tengo una matriz A [], todos menos uno de cuyos elementos aparece varias veces que es un múltiplo de 15, p. 2 ocurre 30 veces, 3 ocurre 45 veces. Pero un elemento ocurre x veces donde x no es un múltiplo de 15. ¿Cómo imprimo el número x. Estoy buscando una solución lineal sin una tabla hash.Estimación de la frecuencia del elemento de una matriz en O (n) tiempo
Gracias.
Hubo una pregunta similar aquí, en StackOverflow, pero no puedo encontrarla.
Permite usar 3 en lugar de 15, porque será más fácil y creo que es completamente equivalente. La secuencia será 4, 5, 4, 5, 3, 3, 4, 5, en el código binario 100, 101, 100, 101, 11, 11, 100, 101.
Usted puede hacer lo siguiente: suma todos los valores de bit menos significativo de los números y tener resto durante 3 (15 originalmente):
bit1 = (0 + 1 + 0 + 1 + 1 + 1 + 0 + 1) % 3 = 5 % 3 = 2 != 0
si es != 0 entonces que bit es igual a 1 en número que estamos tratando de encontrar. Ahora vamos a pasar a la siguiente:
bit2 = (0 + 0 + 0 + 0 + 1 + 1 + 0 + 0) % 3 = 2 % 3 = 2 != 0
bit3 = (1 + 1 + 1 + 1 + 0 + 0 + 1 + 1) % 3 = 6 % 3 = 0 == 0
Así tenemos bit3 == 0, bit2 != 0, bit1 != 0, haciendo 011. Convierte a decimal: 3.
La complejidad espacial es O(1) y complejidad del tiempo es O(n * BIT_LENGTH_OF_VARS), donde BIT_LENGTH_OF_VARS == 8 a byte, BIT_LENGTH_OF_VARS == 32 para int, etc. Por lo tanto, puede ser grande, pero constantes no afectan el comportamiento asintótico y O(n * BIT_LENGTH_OF_VARS) es realmente O(n).
Eso es todo!
¡Ahh, iba a decir hash-table! :) – leppie
@leppie si quieres tener hashtable que tenga garantizado 'O (1)' será '2^32' de tamaño que es delirante. de lo contrario, no puede acceder a 'O (n)' – Andrey
duplicado de http://stackoverflow.com/questions/3963409/interview-question-dealing-with-m-occurrences-among-n – Nabb