查找数组中的对数(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