Giả sử chúng ta có hai mảng X và Y là các số nguyên dương. Tìm số cặp sao cho x ^ y> y ^ x, trong đó x là phần tử của X và y là phần tử của Y. Giả sử X =[2, 1, 6] và Y =[1, 5] , thì đầu ra sẽ là 3. Vì có ba cặp, đó là (2, 1), (2, 5) và (6, 1)
Chúng tôi có thể giải quyết vấn đề này một cách hiệu quả. Logic rất đơn giản, nó sẽ là khi y> x thì x ^ y> y ^ x với một số ngoại lệ. Vì vậy, đây là thủ thuật.
-
Sắp xếp mảng Y
-
với mỗi phần tử x trong X, chúng ta phải tìm chỉ số của số nhỏ nhất lớn hơn x trong Y. Chúng ta sẽ sử dụng tìm kiếm nhị phân để làm như vậy. Nếu không, chúng ta cũng có thể sử dụng hàm upper_bound ().
-
Tất cả số sau chỉ mục tìm được thỏa mãn mối quan hệ nên chỉ cần thêm số đó vào số đếm.
Ví dụ
#include <iostream>
#include <algorithm>
using namespace std;
int count(int x, int Y[], int n, int no_of_y[]) {
if (x == 0)
return 0;
if (x == 1)
return no_of_y[0];
int* index = upper_bound(Y, Y + n, x);
int ans = (Y + n) - index;
ans += (no_of_y[0] + no_of_y[1]);
if (x == 2)
ans -= (no_of_y[3] + no_of_y[4]);
if (x == 3)
ans += no_of_y[2];
return ans;
}
int howManyPairs(int X[], int Y[], int m, int n) {
int no_of_y[5] = {0};
for (int i = 0; i < n; i++)
if (Y[i] < 5)
no_of_y[Y[i]]++;
sort(Y, Y + n);
int total_pairs = 0;
for (int i=0; i< m; i++)
total_pairs += count(X[i], Y, n, no_of_y);
return total_pairs;
}
int main() {
int X[] = {2, 1, 6};
int Y[] = {1, 5};
int m = sizeof(X)/sizeof(X[0]);
int n = sizeof(Y)/sizeof(Y[0]);
cout << "Total pair count: " << howManyPairs(X, Y, m, n);
} Đầu ra
Total pair count: 3