Frequenza stimata dell'elemento di un array nel tempo O (n)

Question

Suppongo che il titolo potrebbe essere un po 'fuorviante, ma non riuscivo a pensarne uno migliore. Ho una matrice A [], tutti tranne uno dei cui elementi si verifica un numero di volte superiore a 15, ad es. 2 si verifica 30 volte, 3 si verifica 45 volte. Ma un elemento si verifica x volte in cui x non è un multiplo di 15. Come posso stampare il numero x. Sto cercando una soluzione lineare senza un hash-table.

Grazie.

Answer 1

C'era una domanda simile qui, su StackOverflow, ma non riesco a trovarla.

Consente di utilizzare 3 invece di 15, perché sarà più semplice e penso che sia completamente equivalente. La sequenza sarà 4, 5, 4, 5, 3, 3, 4, 5, in binario 100, 101, 100, 101, 11, 11, 100, 101.

È possibile effettuare le seguenti operazioni: somma di tutti i valori in bit meno significativo di numeri e prendere parte restante più di 3 (15 in origine):

bit1 = (0 + 1 + 0 + 1 + 1 + 1 + 0 + 1) % 3 = 5 % 3 = 2 != 0

se è != 0 allora che bit è uguale a 1 in numero che stiamo cercando di trovare. Ora consente di passare alla successiva:

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

Così abbiamo bit3 == 0, bit2 != 0, bit1 != 0, rendendo 011. Converti in decimale: 3.

La complessità spaziale è O(1) e complessità temporale è O(n * BIT_LENGTH_OF_VARS), dove BIT_LENGTH_OF_VARS == 8 per byte, BIT_LENGTH_OF_VARS == 32 per int, ecc Così può essere grande, ma le costanti non influenzano il comportamento asintotico e O(n * BIT_LENGTH_OF_VARS) è davvero O(n).

Questo è tutto!