Tìm số cặp vợ chồng có cùng sự khác biệt trong một mảng được sắp xếp

Question

Đây là một câu hỏi phỏng vấn.

"Cho một mảng được sắp xếp. Tìm số cặp vợ chồng có cùng sự khác biệt". Ví dụ:

ví dụ: nếu mảng là {1, 2, 3, 5, 7, 7, 8, 9};

sau đó chúng tôi có

5 cặp với sự khác biệt của 1

6 cặp với sự khác biệt của 2

4 cặp với sự khác biệt của 4

2 cặp với sự khác biệt của 3

4 cặp với sự khác biệt của 6

3 cặp với sự khác biệt của 5

2 cặp với sự khác biệt của 7

1 cặp với sự khác biệt của 8

1 cặp với chênh lệch từ 0

tôi thử như sau:

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

đây là giải pháp O (k * n * logn) trong đó k là chênh lệch lớn nhất giữa phần tử đầu tiên và cuối cùng của mảng được sắp xếp, n là kích thước mảng.

Có ai có ý tưởng nào tốt hơn điều này không?

Answer 1

Có vẻ như phức tạp không cần thiết và tôi không thấy đầy đủ những gì bạn đang làm. Vấn đề không được giải quyết chỉ bằng:

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

Đây là O (n ** 2).

BTW, bạn đã không liệt kê một cặp với sự khác biệt 8 hoặc một cặp với sự khác biệt 0. Mục đích?

Edit:

Logic chỉ là: nhìn vào mỗi cặp trong mảng ban đầu. Mỗi cặp tạo thành một sự khác biệt. Tăng số lượt truy cập cho sự khác biệt đó.

Sửa 2:

Theo yêu cầu của bạn, sau đây là kết quả xét nghiệm của tôi:

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 

Cũng như các chương trình hoàn chỉnh:

#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

Điều này có thể được giải quyết trong thời gian O (k * log k) (trong đó k là sự khác biệt tối đa) nếu bạn sử dụng Fourier transform để nhân các đa thức.

Xem xét vấn đề sau: có hai bộ A = a_1, ..., a_n và B = b_1, ..., b_m, cho mỗi X tìm số cặp (i, j) sao cho a_i + b_j = X. Nó có thể được giải quyết như sau.

Cho phép Pa = x ** a_1 + ... + x ** a_n, Pb = x ** b_1 + ... + x ** b_m. Nếu bạn nhìn vào Pa * Pb, bạn có thể thấy rằng hệ số cho x ** R là câu trả lời cho vấn đề X = R. Vì vậy, nhân các đa thức này bằng biến đổi Fourier, và bạn sẽ tìm câu trả lời cho mọi X trong O (n * log n).

Sau đó, sự cố của bạn có thể bị giảm xuống thành câu hỏi A = arr_1, ..., arr_n, B = -arr_1, ..., -arr_n và dịch chuyển (thêm hằng số) vào mọi giá trị của A và B để làm cho chúng nằm giữa 0 và k.

Answer 3

Điều này không thể giải quyết tốt hơn O (n^2) đối với mảng đầu vào chung vì một số đầu vào dẫn đến kết quả đầu ra khác nhau O (n^2). Ví dụ: thật dễ dàng để tạo một mảng trong đó mỗi cặp phần tử có sự tách biệt khác nhau.

---

Câu hỏi có ý nghĩa hơn nếu nó yêu cầu số cặp có một số sự tách biệt được chỉ định. Điều đó có thể được thực hiện trong thời gian tuyến tính và sử dụng thực tế là sắp xếp của mảng. Không thực sự có ý nghĩa để cung cấp cho một mảng được sắp xếp nếu tốt nhất chúng ta có thể làm là chậm hơn so với phân loại.