Finden Sie die Anzahl der Paare mit dem gleichen Unterschied in einem sortierten Array

Question

Dies ist ein Interview Frage.

"Gegeben ein sortiertes Array. Finden Sie die Anzahl der Paare mit dem gleichen Unterschied."

Beispiel: wenn Array ist {1, 2, 3, 5, 7, 7, 8, 9};

dann haben wir

5 Paare mit Differenz von 1

6 Paare mit Differenz von 2

4 Paare mit Differenz von 4

2 Paare mit Unterschied von 3

4 Paare mit Differenz von 6

3 Paar mit Unterschied von 5

2 paarweise mit Unterschied von 7

1 Paar mit Differenz von 8

1 Paar mit Differenz von 0

versuchte ich folgend:

maxdiff=arr[n-1]-arr[0]; //calculating the maximum difference 
int b[maxdiff]; 
for(i=0;i<maxdiff;i++) 
{ 
for(j=0;j<n;j++) 
{ 
    p=arr[j]+i; 
    x=binarysearch(p,arr); //search p in array,where x return 0/1 
    if(x==1) 
    b[i]++; 
} 
} 

Dies ist O (k * n * logn) -Lösung, wobei k die maximale Differenz zwischen dem ersten und letzten Element eines sortierten Arrays ist, n die Array-Größe.

Hat jemand eine bessere Idee als das?

Answer 1

Es scheint unnötig kompliziert und ich sehe nicht ganz, was Sie tun. Ist das Problem nicht gelöst nur durch:

Dies ist O (n ** 2).

BTW, Sie haben nicht das eine Paar mit einer Differenz von 8 oder das eine Paar mit einer Differenz von 0 aufgeführt. Mit Absicht?

Edit:

Die Logik gerade ist: in der ursprünglichen Anordnung an jedem Paar aussehen. Jedes Paar bildet einen Unterschied. Erhöhe den Zähler für diesen Unterschied.

Edit 2:

Auf Wunsch sind hier meine Testergebnisse:

C:\src>a 
diff: 0 pairs: 1 
diff: 1 pairs: 5 
diff: 2 pairs: 6 
diff: 3 pairs: 2 
diff: 4 pairs: 4 
diff: 5 pairs: 3 
diff: 6 pairs: 4 
diff: 7 pairs: 2 
diff: 8 pairs: 1 

Neben dem kompletten Programm:

#include <iostream> 
using namespace std; 

int main (int argc, char *argv[]) 
{ 
    int n=8; 
    int arr[] = {1,2,3,5,7,7,8,9}; 
    int i, j; 

    int maxdiff=arr[n-1]-arr[0]; //calculating the maximum difference 
    int b[maxdiff]; 

    for(i=0;i<=maxdiff;i++) 
    { 
     b[i]=0; 
    } 

    for(i=0;i<n;i++) 
    { 
     for(j=0;j<i;j++) // note: <i instead of <n 
     { 
      b[arr[i]-arr[j]]++; 
     } 
    } 

    for (i=0;i<=maxdiff;++i) 
    cout<<"diff: "<<i<<" pairs: "<<b[i]<<endl; 
} 

Answer 2

Dies kann in O gelöst werden (k * log k) (wobei k eine maximale Differenz ist), wenn Sie Fourier transform für die Multiplikation von Polynomen verwenden.

Betrachten Sie das folgende Problem: zwei Sätze haben A = a_1, ..., a_n und B = b_1, ..., b_m, für jedes X die Anzahl der Paare (i, j) so finden, dass a_i + b_j = X. Es kann wie folgt gelöst werden.

Sei Pa = x ** a_1 + ... + x ** a_n, Pb = x ** b_1 + ... + x ** b_m. Wenn Sie Pa * Pb betrachten, stellen Sie vielleicht fest, dass der Koeffizient für x ** R eine Antwort für das Problem ist, wo X = R ist. Also multiplizieren Sie diese Polynome mit der Fourier-Transformation, und Sie finden die Antwort für jedes X in O (n * log n).

Danach kann Ihr Problem auf dieses reduziert werden sagen A = arr_1, ..., arr_n, B = -arr_1, ..., -arr_n und Verschieben (Hinzufügen einer Konstante) zu jedem Wert von A und B um sie zwischen 0 und k liegen zu lassen.

Answer 3

Dies kann nicht in besser als O (n^2) für allgemeine Eingabe-Arrays gelöst werden, da einige Eingaben zu O (n^2) verschiedenen Ausgaben führen. Z. B. ist es leicht, ein Array zu konstruieren, bei dem jedes Paar von Elementen einen unterschiedlichen Abstand aufweist.

---

Die Frage macht mehr Sinn, wenn man nach der Anzahl der Paare fragt, die eine bestimmte Trennung haben. Dies kann in linearer Zeit erfolgen und verwendet die Tatsache, dass das Array sortiert ist. Es macht keinen Sinn, ein sortiertes Array zu geben, wenn das Beste, was wir tun können, langsamer ist als das Sortieren.