Costruisce una matrice da una matrice esistente

Question

Costruisce una matrice da una matrice esistente

#1 da (3 voti)

-4

Given an array of integers A[1...n-1] where 'N' is the length of array A[ ]. Construct an array B such that B[i] = min(A[i], A[i+1], ..., A[i+K-1]), where K will be given.

La matrice B avrà elementi N-K + 1.

Possiamo risolvere il problema usando min-heap Costruisci min-heap per k elementi - O (k) Per ogni elemento successivo cancella il primo elemento e inserisci il nuovo elemento e ingrandisci Quindi il peggior tempo di maiuscolo - O ((n-k + 1) * k) + O (k) Spazio - O (k)

Possiamo farlo meglio?

algorithms heap

posta Luv 22.06.2012 - 16:52

fonte

1 risposta

Leggi altre domande sui tag algorithms heap

GIT - come confermare la proprietà del repository Scrivere un'applicazione che chiama un'altra applicazione per alcune attività: come funziona?

score 3 · Answer 1

Ecco il mio primo pensiero, potrebbe non essere la soluzione migliore, ma qui va.

Dai uno sguardo allo schema seguente per K = 10, N = 15

Si può vedere che quando si calcola ciascun valore di B, è necessario utilizzare gli elementi di A [S], A [S + 1], ..., A [E]. Quindi puoi fare questo calcolo e memorizzarlo per primo, poi con ogni iterazione usa il valore memorizzato con gli altri valori A, quindi salvando alcune iterazioni.

Ad esempio,

B [2] = Min (valore salvato, a [2 ... 4], a [10 ... 11])

Questo salva 3 confronti con ogni iterazione.