Come trovare una coppia con k più grande sum?

Dati due matrici ordinate di numeri, vogliamo trovare la coppia con la k più grande sum ansible. (Una coppia è un elemento dal primo array e un elemento dal secondo array). Ad esempio, con matrici

  • [2, 3, 5, 8, 13]
  • [4, 8, 12, 16]

Le coppie con somme maggiori sono

  • 13 + 16 = 29
  • 13 + 12 = 25
  • 8 + 16 = 24
  • 13 + 8 = 21
  • 8 + 12 = 20

Quindi la coppia con la quarta più grande è (13, 8). Come trovare la coppia con la k più grande sum ansible?

Inoltre, qual è l’algoritmo più veloce? Gli array sono già ordinati e le taglie M e N.


Sono già a conoscenza della soluzione O (Klogk) , utilizzando Max-Heap qui indicato.

È anche una delle domande più frequenti nell’intervista su Google e richiedono una soluzione O (k) .

Ho anche letto da qualche parte che esiste una soluzione O (k) , che non riesco a capire.

Qualcuno può spiegare la soluzione corretta con uno pseudocodice.

PS Si prega di NON postare questo link come risposta / commento. NON contiene la risposta.

Comincio con un algoritmo semplice ma non del tutto lineare. Scegliamo un valore tra array1[0]+array2[0] e array1[N-1]+array2[N-1] . Quindi determiniamo quante coppie di somme sono maggiori di questo valore e quante di esse sono inferiori. Questo può essere fatto iterando gli array con due puntatori: puntatore al primo array incrementato quando sum è troppo grande e puntatore al secondo array decrementato quando sum è troppo piccolo. Ripetendo questa procedura per valori diversi e usando la ricerca binaria (o la ricerca binaria unilaterale) potremmo trovare la sum K più grande in tempo O (N log R), dove N è la dimensione dell’array più grande e R è il numero di valori possibili tra array1[N-1]+array2[N-1] e array1[0]+array2[0] . Questo algoritmo ha una complessità temporale lineare solo quando gli elementi dell’array sono numeri interi limitati da una piccola costante.

L’algoritmo precedente può essere migliorato se interrompiamo la ricerca binaria non appena il numero di somme di coppia nell’intervallo di ricerca binaria diminuisce da O (N 2 ) a O (N). Quindi riempiamo l’array ausiliario con queste coppie di somme (questo può essere fatto con un algoritmo a due puntatori leggermente modificato). E poi usiamo l’algoritmo quickselect per trovare la sum K più grande in questo array ausiliario. Tutto ciò non migliora la complessità del caso peggiore perché abbiamo ancora bisogno di O (log R) passi di ricerca binaria. Cosa succede se manteniamo la parte quickselect di questo algoritmo ma (per ottenere un intervallo di valori adeguato) usiamo qualcosa di meglio della ricerca binaria?

Potremmo stimare la gamma di valori con il seguente trucco: ottenere ogni secondo elemento da ogni matrice e cercare di trovare la sum della coppia con il rango k/4 per questi semiarranaggi (usando lo stesso algoritmo in modo ricorsivo). Ovviamente questo dovrebbe dare qualche approssimazione per il range di valori necessario. E in effetti una variante leggermente migliorata di questo trucco fornisce un intervallo contenente solo elementi O (N). Ciò è dimostrato nel seguente documento: “Selezione in X + Y e matrici con righe e colonne ordinate” di A. Mirzaian e E. Arjomandi . Questo documento contiene una spiegazione dettagliata dell’algoritmo, prove, analisi della complessità e pseudo-codice per tutte le parti dell’algoritmo eccetto Quickselect . Se è richiesta la complessità del caso peggiore lineare, Quickselect può essere aumentato con l’algoritmo Median of medians .

Questo algoritmo ha complessità O (N). Se uno degli array è più corto di un altro array (M

Se k N (N-1), è meglio risolvere il problema opposto: k’th sum più piccola.

Ho caricato la semplice implementazione di C ++ 11 su ideone . Il codice non è ottimizzato e non completamente testato. Ho cercato di renderlo il più vicino ansible allo pseudo-codice nella carta collegata. Questa implementazione utilizza std::nth_element , che consente la complessità lineare solo in media (non nel peggiore dei casi).


Un approccio completamente diverso per trovare la sum K’th in tempo lineare è basato su priority queue (PQ). Una variante consiste nell’inserire la coppia più grande in PQ, quindi rimuovere ripetutamente la parte superiore di PQ e inserire invece fino a due coppie (una con indice decrementato in una matrice, l’altra con indice decrementato in altra matrice). E prendere alcune misure per impedire l’inserimento di coppie duplicate. Un’altra variazione consiste nell’inserire tutte le coppie possibili che contengono l’elemento più grande del primo array, quindi rimuovere ripetutamente la parte superiore di PQ e inserire invece la coppia con indice decrementato nel primo array e lo stesso indice nel secondo array. In questo caso non è necessario preoccuparsi dei duplicati.

OP cita la soluzione O (K log K) in cui PQ è implementato come max-heap. Ma in alcuni casi (quando gli elementi dell’array sono distribuiti uniformsmente interi, con un range limitato e la complessità lineare è necessaria solo in media, non nel peggiore dei casi), potremmo usare la coda di priorità del tempo O (1), ad esempio, come descritto in questo documento: ” Una coda di priorità di complessità O (1) per le simulazioni dinamiche molecolari guidate da eventi “di Gerald Paul . Ciò consente la complessità temporale attesa di O (K).

Il vantaggio di questo approccio è la possibilità di fornire i primi elementi K nell’ordine ordinato. Gli svantaggi sono la scelta limitata del tipo di elemento dell’array, l’algoritmo più complesso e più lento, la peggiore complessità asintotica: O (K)> O (N).

EDIT: questo non funziona. Lascio la risposta, poiché apparentemente non sono l’unico a poter avere questo tipo di idea; guarda la discussione qui sotto. Un contro-esempio è x = (2, 3, 6), y = (1, 4, 5) e k = 3, dove l’algoritmo fornisce 7 (3 + 4) invece di 8 (3 + 5).


Sia y siano i due array, ordinati in ordine decrescente; vogliamo build la K -la più grande sum.

Le variabili sono: i l’indice nel primo array (elemento x[i] ), j l’indice nel secondo array (elemento y[j] ), e k l'”ordine” della sum ( k in 1..K ), nel senso che S(k)=x[i]+y[j] sarà la k -la sum maggiore che soddisfa le tue condizioni (questo è il ciclo invariante).

Inizia da (i, j) uguale a (0, 0) : chiaramente, S(1) = x[0]+y[0] .

per k da 1 a K-1 , fai:

  • se x[i+1]+ y[j] > x[i] + y[j+1] , allora i := i+1 (e j non cambia); altrimenti j:=j+1

Per vedere che funziona, considera di avere S(k) = x[i] + y[j] . Quindi, S(k+1) è la sum più grande che è inferiore (o uguale) a S(k) , e come almeno un elemento ( i o j ) cambia. Non è difficile vedere che esattamente uno di i o j debba cambiare. Se cambio, la sum maggiore che puoi build è inferiore a S(k) è impostando i=i+1 , perché x sta decrescendo e tutti i x[i'] + y[j] con i' < i maggiore di S(k) . Lo stesso vale per j , che mostra che S(k+1) è x[i+1] + y[j] o x[i] + y[j+1] .

Pertanto, alla fine del ciclo hai trovato la sum maggiore di K -th.

tl; dr: Se guardi avanti e guardi indietro ad ogni iterazione, puoi iniziare con la fine (che è più alta) e tornare indietro nel tempo O(K) .

Sebbene l’intuizione alla base di questo approccio sia, credo, valida, il codice sottostante non è del tutto corretto al momento (vedi commenti).


Vediamo: prima di tutto, gli array sono ordinati. Quindi, se gli array sono b con le lunghezze M e N , e come li hai disposti, gli oggetti più grandi si trovano rispettivamente nelle slot M e N , la coppia più grande sarà sempre a[M]+b[N] .

Ora, qual è la seconda coppia più grande? Avrà forse uno di {a[M],b[N]} (non può avere entrambi, perché è di nuovo la coppia più grande), e almeno uno di {a[M-1],b[N-1]} . MA, sappiamo anche che se scegliamo a[M-1]+b[N-1] , possiamo ingrandire uno degli operandi scegliendo il numero più alto dalla stessa lista, quindi avrà esattamente un numero dal ultima colonna e una dalla penultima colonna.

Considera i seguenti due array: a = [1, 2, 53]; b = [66, 67, 68] a = [1, 2, 53]; b = [66, 67, 68] . La nostra coppia più alta è 53+68 . Se perdiamo il più piccolo di questi due, la nostra coppia è 68+2 ; se perdiamo il più grande, è 53+67 . Quindi, dobbiamo guardare avanti per decidere quale sarà la nostra prossima coppia. La strategia di lookahead più semplice è semplicemente quella di calcolare la sum di entrambe le coppie possibili. Ciò costerà sempre due aggiunte e due confronti per ogni transizione (tre perché dobbiamo affrontare il caso in cui le somme sono uguali), chiamiamolo quel costo Q ).

All’inizio, ero tentato di ripetere quella K-1 volte. Ma c’è un intoppo: la prossima coppia più grande potrebbe effettivamente essere l’altra coppia che possiamo fare validamente da {{a[M],b[N]}, {a[M-1],b[N-1]} . Quindi, dobbiamo anche guardare dietro.

Quindi, cerchiamo di codice (python, dovrebbe essere compatibile 2/3):

 def kth(a,b,k): M = len(a) N = len(b) if k > M*N: raise ValueError("There are only %s possible pairs; you asked for the %sth largest, which is impossible" % M*N,k) (ia,ib) = M-1,N-1 #0 based arrays # we need this for lookback nottakenindices = (0,0) # could be any value nottakensum = float('-inf') for i in range(k-1): optionone = a[ia]+b[ib-1] optiontwo = a[ia-1]+b[ib] biggest = max((optionone,optiontwo)) #first deal with look behind if nottakensum > biggest: if optionone == biggest: newnottakenindices = (ia,ib-1) else: newnottakenindices = (ia-1,ib) ia,ib = nottakenindices nottakensum = biggest nottakenindices = newnottakenindices #deal with case where indices hit 0 elif ia <= 0 and ib <= 0: ia = ib = 0 elif ia <= 0: ib-=1 ia = 0 nottakensum = float('-inf') elif ib <= 0: ia-=1 ib = 0 nottakensum = float('-inf') #lookahead cases elif optionone > optiontwo: #then choose the first option as our next pair nottakensum,nottakenindices = optiontwo,(ia-1,ib) ib-=1 elif optionone < optiontwo: # choose the second nottakensum,nottakenindices = optionone,(ia,ib-1) ia-=1 #next two cases apply if options are equal elif a[ia] > b[ib]:# drop the smallest nottakensum,nottakenindices = optiontwo,(ia-1,ib) ib-=1 else: # might be equal or not - we can choose arbitrarily if equal nottakensum,nottakenindices = optionone,(ia,ib-1) ia-=1 #+2 - one for zero-based, one for skipping the 1st largest data = (i+2,a[ia],b[ib],a[ia]+b[ib],ia,ib) narrative = "%sth largest pair is %s+%s=%s, with indices (%s,%s)" % data print (narrative) #this will work in both versions of python if ia <= 0 and ib <= 0: raise ValueError("Both arrays exhausted before Kth (%sth) pair reached"%data[0]) return data, narrative 

Per quelli senza pitone, ecco un ideone: http://ideone.com/tfm2MA

Nel peggiore dei casi, abbiamo 5 confronti in ogni iterazione e iterazioni K-1, il che significa che si tratta di un algoritmo O (K).

Ora, potrebbe essere ansible sfruttare le informazioni sulle differenze tra i valori per ottimizzarlo un po ', ma questo raggiunge l'objective.


Ecco un'implementazione di riferimento (non O(K) , ma funzionerà sempre, a meno che non ci sia un caso d'angolo con casi in cui le coppie hanno somme uguali):

 import itertools def refkth(a,b,k): (rightia,righta),(rightib,rightb) = sorted(itertools.product(enumerate(a),enumerate(b)), key=lamba((ia,ea),(ib,eb):ea+eb)[k-1] data = k,righta,rightb,righta+rightb,rightia,rightib narrative = "%sth largest pair is %s+%s=%s, with indices (%s,%s)" % data print (narrative) #this will work in both versions of python return data, narrative 

Questo calcola il prodotto cartesiano dei due array (cioè tutte le coppie possibili), li ordina per sum e prende l'elemento kth. La funzione di enumerate decora ogni object con il suo indice.

L’algoritmo max-heap nell’altra domanda è semplice, veloce e corretto. Non bussare. È anche ben spiegato. https://stackoverflow.com/a/5212618/284795

Potrebbe esserci non c’è alcun algoritmo O (k). Va bene, O (k log k) è quasi altrettanto veloce.

Se le ultime due soluzioni erano a (a1, b1), (a2, b2), allora mi sembra che ci siano solo quattro soluzioni candidate (a1-1, b1) (a1, b1-1) (a2-1, b2 ) (a2, b2-1). Questa intuizione potrebbe essere sbagliata. Sicuramente ci sono al massimo quattro candidati per ogni coordinata, e il successivo più alto è tra le 16 coppie (a in {a1, a2, a1-1, a2-1}, b in {b1, b2, b1-1, b2- 1}). Va bene).

(No non lo è, ancora non sono sicuro che sia ansible.)

 [2, 3, 5, 8, 13] [4, 8, 12, 16] 

Unisci i 2 array e annota gli indici nell’array ordinato. Ecco come appare l’array di indici (a partire da 1 non 0)

[1, 2, 4, 6, 8] [3, 5, 7, 9]

Ora inizia dalla fine e crea le tuple. sum gli elementi nella tupla e scegli la k più grande sum.