C++程序 计算唯一三元组的XOR为零

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的三元组。下面给出计算唯一三元组数量的步骤:

以下是此方法的完整算法:

  1. 使用哈希表标记所有数组元素。
  2. 运行两个嵌套循环,一个从i-n-1,另一个从i+1-n,以获取所有对。
  3. 获取对的XOR。
  4. 检查XOR是否为数组元素而不是ai或aj。
  5. 如果条件成立,则增加计数。
  6. 返回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)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例