intersezione elementi array

[metiu0003]

Buongiorno a tutti,
avrei questo esercizio da risolvere: Dati due vettori A e B (lunghi n ed m, rispettivamente) che rispettano il vincolo 1 e con distanza massima fra numeri comuni pari a k (costante), determinare in modo efficiente tutti e soli i numeri presenti contemporaneamente in A e B, nello stesso ordine in cui compaiono,
utilizzando al massimo O(k) (cioè O(1)) spazio aggiuntivo rispetto allo spazio per l’input.

Il vincolo 1 è : per ogni posizione i e j nel vettore A e per ogni posizione i' e j' nel vettore B: se A[i] = B[i'] ∧ A[j] = B[j'] ∧ i < j allora i'< j'. Cioè in altre parole i numeri in comune compaiono nello stesso ordine nei due vettori e la distanza tra due numeri comuni consecutivi in un vettore è <= a k.

Ad esempio:
A= 3 7 5 9 10 15 16 1 6 2
B= 4 8 5 13 1 17 2 11
quindi m = 10, n = 8, k = 6
il risultato è 5 1 2

[wingman87]

L'esercizio è carino ma l'esempio è sbagliato...
Comunque dov'è che ti incarti?

[metiu0003]

si scusa l'esempio giusto è:
A= 3 7 5 9 10 15 16 1 6 5
B= 4 8 5 13 1 17 2 11
quindi m = 10, n = 8, k = 6
il risultato è 5 1 2


Io pensavo di partire cercando il primo elemento comune ad entrambi i vettori e poi confrontare i successivi k elementi di entrambi i vettori per trovare l'eventuale elemento comune successivo. Però credo che sicuramente ci sia una soluzione migliore della mia, magari qualcosa che non sfrutta l'ordinamento.

[wingman87]

Secondo me devi sfruttare sin dal principio la distanza k, quindi anche nella ricerca della prima occorrenza. Inoltre l'esercizio ti permette di utilizzare O(k) spazio aggiuntivo e questo potrebbe permetterti di adottare un algoritmo più rapido.
Comunque l'esempio è ancora sbagliato (in A non è presente 2)

[metiu0003]

Adesso dovrebbe essere giusto.
Comunque avevo pensato anch'io di fare circa cosi però non mi viene in mente come fare. Riusciresti a farmi un esempio, qualcosa tipo pseudocodice magari.

[wingman87]

Quali strutture dati conosci?

[metiu0003]

Vanno bene tutte: liste, heap, code, stack, alberi bst o red black ma possibilmente non tabelle hash.

[wingman87]

Ci ho pensato un po' ma c'è una questione che non mi torna... Per come è posto il problema i primi due numeri in comune potrebbero trovarsi in qualunque posizione in A e in B, ad esempio alla posizione 1 in A e alla posizione 100 in B. C'è qualche considerazione aggiuntiva in merito?
Inoltre una soluzione banale ma che credo non sia concessa è ordinare uno dei due array e poi scorrere l'altro cercando i vari numeri nel primo (ricerca dicotomica). Non credo sia concessa perché uno degli input viene irrimediabilmente modificato...

[metiu0003]

Infatti il problema è la posizione del primo numero in comune. Oltre a quello che ti ho detto non c'è nient'altro altro. La soluzione banale non usa k quindi non va bene.

[metiu0003]

Il primo elemento in comune si trova in posizione 0,k-1.

[metiu0003]

Ci ho pensato un po' ma c'è una questione che non mi torna... Per come è posto il problema i primi due numeri in comune potrebbero trovarsi in qualunque posizione in A e in B, ad esempio alla posizione 1 in A e alla posizione 100 in B. C'è qualche considerazione aggiuntiva in merito?
Inoltre una soluzione banale ma che credo non sia concessa è ordinare uno dei due array e poi scorrere l'altro cercando i vari numeri nel primo (ricerca dicotomica). Non credo sia concessa perché uno degli input viene irrimediabilmente modificato...

Il primo elemento si trova in tra la posizione 0 e la k-1.

[wingman87]

Ok, allora quello che puoi fare è sfruttare una struttura dati per metterci fino a k elementi. Questa struttura deve permetterti di cercare un elemento al suo interno con complessità meno che lineare, compreso l'inserimento (altrimenti non c'è guadagno). Inoltre deve restituirti l'indice dell'elemento cercato.
Grazie a questa struttura puoi metterci i primi k elementi di A e poi uno ad uno cercare gli elementi di B nella struttura. Quando trovi una corrispondenza in A all'indice j, svuoti la struttura e ci metti tutti gli elementi da j+1 a j+k e continui.
Questo come base, poi puoi fare delle migliorie...