Trova il numero di coppie con la stessa differenza in un array ordinato

Question

Questa è un'interrogazione.

"Dato un array ordinato, trova il numero di coppie con la stessa differenza."

ad esempio: se l'array è {1, 2, 3, 5, 7, 7, 8, 9};

allora abbiamo

5 accoppiamenti con differenza di 1

6 accoppiamenti con differenza di 2

4 coppie con differenza di 4

2 coppie con differenza di 3

4 coppie con differenza di 6

3 coppie con differenza di 5

2 coppie con differenza di 7

1 accoppiamento con differenza di 8

1 accoppiamento con differenza di 0

ho provato il seguente:

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]++; 
} 
} 

questa è la soluzione O (k * n * logn) dove k è la differenza massima tra il primo e l'ultimo elemento di un array ordinato, n è la dimensione dell'array.

Qualcuno ha un'idea migliore di questa?

Answer 1

Sembra inutilmente complicato e non vedo completamente quello che stai facendo. Il problema non è risolto semplicemente:

maxdiff=arr[n-1]-arr[0]; //calculating the maximum difference 
int b[maxdiff]; 
for(i=0;i<n;i++) 
{ 
    for(j=0;j<i;j++) // note: <i instead of <n 
    { 
     b[arr[i]-arr[j]]++ 
    } 
} 

Questo è O (n ** 2).

BTW, non hai elencato l'una coppia con una differenza di 8 o una coppia con una differenza di 0. Di proposito?

Edit:

La logica è solo: guardare ogni coppia nella matrice originale. Ogni coppia forma una differenza. Aumentare il contatore per quella differenza.

Edit 2:

Su vostra richiesta, qui sono i miei risultati dei test:

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 

così come il programma completo:

#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

Questo può essere risolto in O (k * log k) (dove k è una differenza massima) se si utilizza Fourier transform per la moltiplicazione dei polinomi.

Considerare il seguente problema: disporre di due set A = a_1, ..., a_n e B = b_1, ..., b_m, per ogni X trova il numero di coppie (i, j) tale che a_i + b_j = X. Può essere risolto come segue.

Lasciate Pa = x ** a_1 + ... + x ** a_n, Pb = x ** b_1 + ... + x ** b_m. Se guardate Pa * Pb, potreste scoprire che il coefficiente per x ** R è una risposta per il problema dove X = R. Quindi, moltiplicate questo polinomio usando la trasformata di Fourier, e troverete la risposta per ogni X in O (n * log n).

Successivamente, il problema potrebbe essere ridotto a questo dicendo A = arr_1, ..., arr_n, B = -arr_1, ..., -arr_n e spostamento (aggiunta di una costante) a ogni valore di A e B per farli stare tra 0 e k.

Answer 3

Questo non può essere risolto in meglio di O (n^2) per gli array di input generali perché alcuni ingressi portano a O (n^2) diverse uscite. Ad esempio, è facile costruire un array in cui ogni coppia di elementi ha una separazione diversa.

---

La domanda ha più senso se si richiede il numero di coppie con una separazione specifica. Questo può essere fatto in tempo lineare e usa il fatto che l'array è ordinato. Non ha senso dare un array ordinato se il meglio che possiamo fare è più lento dell'ordinamento.