Estimación de la frecuencia del elemento de una matriz en O (n) tiempo

Question

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.

Gracias.

Answer 1

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!