查找数组中的对数(x，y)，以便在C ++中x ^ y> y ^ x

假设我们有两个正整数数组X和Y。找到对的数量，使得x ^ y> y ^ x，其中x是X的元素，y是Y的元素。假设X = [2，1，6]，并且Y = [1，5] ，则输出将为3。由于有三对，分别是(2,1)，(2,5)和(6,1)

我们可以有效地解决这个问题。逻辑很简单，只有在y> x然后是x ^ y> y ^ x时才会例外。因此，这就是窍门。

• 对数组Y排序

• 对于X中的每个元素x，我们必须找到大于Y中x的最小数字的索引。我们将使用二进制搜索来执行此操作。否则，我们也可以使用upper_bound()函数。

• 找到的索引之后的所有数字都满足该关系，因此只需将其添加到计数中即可。

示例

#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);
}

输出结果

Total pair count: 3