Znajdź liczbę par o tej samej różnicy w posortowanej tablicy

Question

To jest pytanie do wywiadu.

"Biorąc pod uwagę posortowaną tablicę Znajdź liczbę par z tą samą różnicą."

na przykład: jeśli tablica to {1, 2, 3, 5, 7, 7, 8, 9};

wtedy mamy

5 par z różnicą 1

6 par różnicą 2

4 par różnicą 4

2 parami różnicy 3

4 pary z różnicą 6

3 par różnicą 5

dwóch parach z różnicy 7

1 pary z różnicy 8

1 pary z różnicy 0

że próbował następujące:

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

to jest rozwiązanie O (k * n * logn), gdzie k jest maksymalną różnicą między pierwszym i ostatnim elementem posortowanej tablicy, n jest rozmiarem tablicy.

Czy ktoś ma lepszy pomysł niż ten?

Answer 1

Wydaje się niepotrzebnie skomplikowany i nie do końca rozumiem, co robisz. Czy problem nie został rozwiązany przez:

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

To jest O (n ** 2).

Przy okazji nie podano jednej pary z różnicą 8 lub jedną parą z różnicą 0. Celowo?

Edit:

Logika jest tylko: spojrzeć na każdej parze w oryginalnej tablicy. Każda para tworzy różnicę. Zwiększ licznik tej różnicy.

Edit 2:

Na Państwa życzenie, oto wyniki badań moi:

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 

jak również kompletny program:

#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

ten może być rozwiązany w czasie O (k * log k) (gdzie k jest maksymalną różnicą), jeśli używasz Fourier transform do mnożenia wielomianów.

Weź pod uwagę następujący problem: posiadanie dwóch zestawów A = a_1, ..., a_n i B = b_1, ..., b_m, dla każdego X znajdź liczbę par (i, j) taką, że a_i + b_j = X. Można to rozwiązać w następujący sposób.

Niech Pa = x ** a_1 + ... + x ** a_n, Pb = x ** b_1 + ... + x ** b_m. Jeśli spojrzysz na Pa * Pb, może się okazać, że współczynnik dla x ** R jest odpowiedzią na problem, w którym X = R. Więc pomnóż te wielomiany za pomocą transformaty Fouriera, a znajdziesz odpowiedź dla każdego X w O (n * log n).

Następnie problem może zostać zredukowany do tego, mówiąc: A = arr_1, ..., arr_n, B = -arr_1, ..., -arr_n i przesunięcie (dodanie stałej) do każdej wartości A i B aby ustawić je między 0 a k.

Answer 3

Nie można tego rozwiązać lepiej niż O (n^2) w przypadku ogólnych tablic wejść, ponieważ niektóre wejścia prowadzą do różnych wyjść O (n^2). Np. Łatwo zbudować tablicę, w której każda para elementów ma inną separację.

Pytanie ma więcej sensu, jeśli chodzi o liczbę par, które mają określoną separację. Można to zrobić w czasie liniowym i wykorzystuje fakt, że tablica jest posortowana. Naprawdę nie ma sensu dawać posortowanej tablicy, jeśli najlepsze, co możemy zrobić, to wolniejsze niż sortowanie.