OliForum Matematico

Questo non è certo originale ma è sempre carino per chi non lo conosce già:
Determinare se in un array di interi c'è un valore che si ripete più della metà delle volte usando spazio costante e senza alterare l'array.
La soluzione banale prende tempo quadratico ma esiste qualcosa di molto migliore che lascio a voi trovare. Ciao.

Beh, così su due piedi, mi verrebbe da fare un sort dell'array. A questo punto, i valori uguali saranno tutti vicini, quindi userei una variabile che mi scorre il vettore e che incrementa di uno ogni volta che l'elemento che sta consderando è uguale al precedente, mentre si azzera appena ne trova uno diverso, ricominciando così la conta. Se durante il ciclo, il valore della variabile supera n/2 (considerando con n il valore della lunghezza dell'array), allora vuol dire che il valore che sta considerando si ripete per più della metà.
Così è un po' più ottimizzato di un quadratico, anche se probabilmente si può trovare qualcosa di ancora migliore... Va beh vorrà dire che ci penserò un altro po'!

Ah però così altero l'array, mi ero dimenticata dell'ultima parte del tuo messaggio... Beh allora come non detto, penserò a qualcos'altro!!

Butto li' un'osservazione che forse e' utile: se c'e' un elemento che si ripete piu' della meta' delle volte, allora compare in 2 posizioni consecutive dell'array.

MindFlyer: provo ad aggiungere qualcosa alla tua osservazione.
Se N è pari e ci sono N/2+1 o più elementi uguali, allora almeno due o più di questi sono consecutivi.
Se N è dispari e ci sono N/2+1 o più elementi uguali, allora possono non esserci due o più elementi uguali consecutivi.

Correggetemi se sbaglio...

E' sufficiente considerare il primo e l'ultimo elemento dell'array come consecutivi...comunque non capisco come possa essere utile

ah io non consideravo l'ultimo e il primo consecutivi...

Sì, scusate per l'imprecisione. Quell'unico caso si esclude in tempo lineare, oppure si riconduce agli altri facendo finta che l'array sia circolare, come volete.
Usare questa cosa in modo sensato, è tutto un altro paio di maniche, però.

Per il caso pessimo non ho idee, ma per il caso medio una soluzione potrebbe essere questa: si prende un elemento a caso e si scorre l'array per vedere se ricorre più di metà delle volte; se sì, si termina, altrimenti si ricomincia da capo.
Sia $ $$ n $$ $ il numero degli elementi, sia $ $$ m $$ $ il numero di passi che vengono eseguiti all'interno del loop "infinito"; $ $$ m $$ $ è lineare rispetto a $ $$ n $$ $. Il numero di passi svolti mediamente sarà al più
$ m \sum_{i=1}^{\infty} i/2^i $. Poichè $ \sum_{i=1}^{\infty} i/2^i $ è convergente, in media l'algoritmo opererà in $ O(m) $ e, quindi, in $ $$ O(n) $$ $.

si puo' abbreviare la tua procedura cosi' volendo

Oooops, ho riletto il problema e mi sono accorto che ho fatto un algoritmo che non c'entra niente. Avevo capito: dato un array con un elemento che ricorre più di metà delle volte, trovare l'elemento usando spazio costante.
Scusate.

Imperterrito, incurante delle figuracce, continuo a sparare algoritmi.
Una soluzione potrebbe essere questa:
1) trovo il valore massimo nell'array, che chiamo max
2) eseguo un ciclo con i che va da 1 a logaritmo in base 2 di max
3) trovo il numero di elementi che, in base 2, terminano con 0 e il numero di elementi che, in base 2, terminano con 1 (si usa il modulo 2, o, meglio, il modulo 2^i)
4) se entrambi i valori sono minori della metà + 1, si termina con insuccesso, altrimenti si prende il valore che ha avuto più hit, per esempio 1, e al ciclo successivo si testano i valori 01 e 11 (modulo 4, cioè 2^2)
5) se entrambi i valori sono minori della metà + 1 si termina con insuccesso, altrimenti si prende il valore che ha avuto più hit, e così via.
Questo sistema permette sia di verificare se un array ha un elemento che ricorre più di metà delle volte, sia di esibire questo elemento (che, nel caso esista, viene "ricostruito" iterazione dopo iterazione).
Il caso peggiore è O(nlog(max)).

L'idea di Ipparco è molto buona. Ma non è ancora la soluzione "vera". Si può risolvere in tempo lineare (questo è già un hint) con un approccio differente ma per nulla sofisticato. Dai, che non è difficile.

Premetto che la mia idea è da affinare, adesso la butto giù giusto in linea teorica e che considero l'array in modo circolare, quindi considero la cella finale come consecutiva a quella iniziale. (e che non sono molto brava a spiegare, quindi farò il possibile per farmi capire ugualmente! )..
Io scorrerei l'array e cercherei qual è la sequenza di lunghezza massima (chiamiamola L) di celle consecutive contenenti uno stesso numero (chiamiamolo A).
A questo punto, come ha detto MindFlyer, perchè possa esistere almeno un elemento che si ripete per più della metà dell'array deve trovarsi almeno in due posizioni consecutive.
Quindi, se L è uguale a 1, non sono presenti elementi che verificano la condizione richiesta. Se è maggiore di 1, andiamo a vedere quante volte nell'array è presente A, e tengo in memoria questo valore in una variabile (C).
Se A è presente per più della metà dell'array, il problema è risolto.
Altrimenti, bisogna chiedersi se è possibile che esista un altro valore nell'array che verifica la condizione richiesta.
Quindi vado a cercare il valore che ha un numero di celle consecutive massimo escluso A. Guardo quante volte si ripete nell'array (e le sommo nella variabile C) e, se neanche questo verifica la condizione, continuo la mia ricerca fino a quando la lunghezza massima di celle consecutive è >1 e C<N/2.

Spero di essere stata più o meno chiara... magari si possono trovare anche altre condizioni per ridurre ulteriorimente il numero di ricorsioni, se mi dite che sono sulla strada giusta provo a pensare anche a quelle!

So praticamente nulla di informatica, comunque ad intuito mi sembra di aver capito che per "spazio costante" si intenda che qualsiasi struttura creata nell'algoritmo deve essere indipendente dalla grandezza dell'input, è giusto?

A =Betta= : il tuo algoritmo, se ho capito bene, conta comunque tutti gli elementi, ma lo fa "in ordine di sospetto", ovvero ritenendo soluzioni più probabili gli elementi con sequenze di lunghezza maggiore. Da dove deriva precisamente questo sospetto? Poi, come si comporta il tuo algoritmo nel caso in cui ci siano due elementi distinti che hanno sequenze di uguale lunghezza massima? Poi, ordinando gli elementi per sospetto, associ una lunghezza L1 a un elemento A, L2 ad un elemento B, ecc. ma dove salvi queste relazioni? La struttura in cui le salvi dipende dal numero di elementi diversi nell'array, e quindi dall'input? (vedi inizio messaggio).