C++程序 计算唯一三元组的XOR为零
给定没有重复项的N个数字,计算唯一三元组(ai,aj,ak)的数量,使它们的XOR为0。如果三元组中的所有三个数字都是唯一的,则称其为唯一的三元组。
示例:
输入:a[] = {1, 3, 5, 10, 14, 15};
输出:2
解释:{1,14,15}和{5,10,15}是其XOR为0的唯一三元组。{1,14,15}和所有其他组合的1,14,15都视为一种。
输入:a[] = {4,7,5,8,3,9};
输出:1
解释:{4, 7, 3}是其XOR为0的唯一三元组
朴素方法: 一个朴素的方法是运行三个内嵌循环,第一个运行从0到n,第二个运行从i+1到n,最后一个从j+1到n,以获取唯一的三元组。计算ai, aj, ak的XOR,检查其是否等于0。如果是,则增加计数。
时间复杂度:O(n3)
高效方法: 一种有效的方法是使用XOR的属性之一:两个相同数字的XOR结果为0。因此,我们只需要计算唯一的对的XOR,如果计算的XOR是数组元素之一,则获得其XOR为0的三元组。下面给出计算唯一三元组数量的步骤:
以下是此方法的完整算法:
- 使用哈希表标记所有数组元素。
- 运行两个嵌套循环,一个从i-n-1,另一个从i+1-n,以获取所有对。
- 获取对的XOR。
- 检查XOR是否为数组元素而不是ai或aj。
- 如果条件成立,则增加计数。
- 返回count / 3,因为我们只想要唯一的三元组。因为i-n和j + 1-n给我们提供了唯一的对,但不是三元组,所以进行count / 3以删除其他两个可能的组合。
以下是上述想法的实现:
// CPP program to count the number of
// unique triplets whose XOR is 0
#include <bits/stdc++.h>
using namespace std;
// function to count the number of
// unique triplets whose xor is 0
int countTriplets(int a[], int n)
{
// To store values that are present
unordered_set<int> s;
for (int i = 0; i < n; i++)
s.insert(a[i]);
// stores the count of unique triplets
int count = 0;
// traverse for all i, j pairs such that j>i
for (int i = 0; i < n-1; i++) {
for (int j = i + 1; j < n; j++) {
// xor of a[i] and a[j]
int xr = a[i] ^ a[j];
// if xr of two numbers is present,
// then increase the count
if (s.find(xr) != s.end() && xr != a[i] &&
xr != a[j])
count++;
}
}
// returns answer
return count / 3;
}
// Driver code to测试上述函数的代码:
// Driver code to test above function
int main()
{
int a[] = {1, 3, 5, 10, 14, 15};
int n = sizeof(a) / sizeof(a[0]);
cout << countTriplets(a, n);
return 0;
}
输出:
2
时间复杂度: O(n2)
辅助空间: 对于unordered_set为O(n)