Dati due array ordinati in ordine ascendente con la stessa lunghezza N, calcola il Kth min a [i] + b [j]. Complessità temporale O (N)

Andiamo con questa formulazione:

Another variant of the question goes like this: given a matrix with sorted rows, and sorted columns, find K^th smallest.

Lascia che M(1,1) denoti l'angolo della matrice con il numero più piccolo e lascia che M(n,n) sia l'angolo con il numero più alto. (ovviamente entrambi sono sulla stessa diagonale di M).

Ora pensiamo alle sotto-matrici: se prendiamo la sottomatrice che va da M(0,0) a M(p,p) otteniamo una matrice che ha il p^2 il valore più piccolo alla posizione M(p,p) e tutti i suoi altri valori sono più piccoli. AND i campi M(0,p)-M(p,p) e M(p,0)-M(p,p) considerati insieme sono costituiti da 2p-1 valori.

Quindi guardiamo solo questi valori:

perché sappiamo con certezza che il più piccolo valore di K ^th è lì dentro.

Quindi il tuo algoritmo desiderato si riduce a (pseudocodice):

p := ceil( sqrt(K) )
candidate_list := merge (M(*,p), M(p,*)) // this has O(p) runtime since both lists are sorted
kth_element := candidate_list[p^2 - k] // +1 if your list starts at 1. 

Poiché la prima e l'ultima riga hanno il tempo di esecuzione O (1), il runtime totale è

O(p) <= O(sqrt(k)+1) <= O(sqrt(n^2)+1) <= O(n+1) <= O(n)

Se hai una coppia di numeri a[i] e b[j] allora il prossimo valore sarà a[i+1] + b[k] con k<=j o a[k] + b[j+1] con k <= i .

Questo significa che puoi ottenere il numero successivo di:

int newI = i+1;
int newJ = j;
for(;newJ>=0 && a[i]+b[j]<a[newI]+b[newJ];newJ--){}
int newI2 = i;
int newJ2 = j+1;
for(;new2I>=0 && a[i]+b[j]<a[new2I]+b[new2J];new2I--){}
if(a[new2I]+b[new2J]<a[newI]+b[newJ])
    //new2I and new2J are the next values
else
    //newI and newJ are the next values

Fai questo K volte, ma non è O (n).