查找数组中对的数量,以使它们的XOR为0  


难度级别 中等
经常问 Cadence印度 优惠券 霍尼韦尔 的确 信息边缘 月蛙实验室 Pinterest
排列 哈希 搜索 排序

假设存在问题“查找数组中的对数,以使其XOR为0”的问题,我们给出了一个 排列 of 整数。 问题语句要求找出数组中存在的对的数量,该对具有 Ai XOR Aj = 0。

注意:1小于或等于 i, i 小于 j 以及 j 小于或等于n(1 <=i < j<= n)。

使用案列  

查找数组中对的数量,以使它们的XOR为0Pin

arr[] = {2, 3, 1, 3, 2}
2

说明

索引(0,4)和(1,3)。

arr[] = {1, 1, 1}
3

算法  

  1. 找出数组中存在的最大元素。
  2. 创建一个大小为数组(最大元素)的数组。
  3. 遍历数组,而i <n(数组的长度)。
    1. 计算并存储我们创建的数组中每个数组元素的频率。
  4. 遍历计数数组,而i <=最大元素。
    1. 输出=输出+ count [i] *(count [i] – 1)吗?
  5. 返回输出/ 2。

说明

我们有一个整数数组。 问题陈述要求找出存在于数组中的对,从而 Ai XOR Aj =0。我们将使用索引映射,这意味着我们将计算每个数组元素的频率,以便我们可以算出它们是否可以进行count [i] * count [i-1]并将结果计入输出。 为了解决这个问题 排列 并在该数组元素的位置作为计数数组的索引,在该位置我们将存储元素的频率,因此,如果在特定位置找到数字,则将其用作索引。

参见
计数和切换二进制数组上的查询

我们将从数组中找到最大元素。 在最大元素大小中,我们将要制作一个数组,这是计数数组,这将用作频率数组。 我们需要遍历数组并存储每个数组元素的计数。 然后我们将输出变量设置为0。

让我们考虑一个例子:

使用案列

arr [] = {2,3,1,3,2}的最大数组大小为3。

i = 0,arr [i] = 2,我们将做count [arr [i]] + = 1,这意味着count元素的第二个索引将增加2。

i = 1,arr [i] = 3,我们将做count [arr [i]] + = 1,这意味着count元素的第二个索引将增加3。

i = 2,arr [i] = 1,我们将做count [arr [i]] + = 1,这意味着count元素的第一个索引将增加1。

i = 3,arr [i] = 3,我们将做count [arr [i]] + = 1,这意味着count元素的第三个索引将增加3。

i = 4,arr [i] = 2,我们将做count [arr [i]] + = 1,这意味着count元素的第二个索引将增加2。

我们将count的数组作为count [] = {0,1,2,2}

我们将遍历此数组,并且每次执行output = output + count [i] *(count [i] – 1)。

它将返回输出为output / 2。

C ++代码查找数组中的对数,以使它们的XOR为0  

#include<iostream>
#include<algorithm>

using namespace std;

int calculate(int a[], int n)
{
    int *maxm = max_element(a, a + 5);
    int count[*maxm + 1] = {0};

    for(int i = 0; i < n; i++)
    {
        count[a[i]] += 1;
    }
    int output = 0;
    for(int i = 0; i < (*maxm)+1; i++)
    {
        output = output + count[i] * (count[i] - 1) ;
    }
    return output/2;
}
int main()
{
    int a[] = {2, 3, 1, 3, 2};
    int n = sizeof(a) / sizeof(a[0]);
    cout <<"XOR Pairs are : "<< (calculate(a,n));
    return 0;
}
XOR Pairs are : 2

Java代码查找数组中的对数,以使它们的XOR为0  

import java.util.Arrays;

class XORPair
{
    public static int calculate(int arr[], int n)
    {
        int max= Arrays.stream(arr).max().getAsInt();

        int count[] = new int[max+ 1];

        for (int i = 0; i < n; i++)
        {
            count[arr[i]] += 1;
        }
        int output = 0;
        for (int i = 0; i < (max) + 1; i++)
        {
            output = output + count[i] * (count[i] - 1);
        }
        return output / 2;
    }
    public static void main(String[] args)
    {
        int a[] = {2, 3, 1, 3, 2};
        int n = a.length;
        System.out.println("XOR Pairs are : "+calculate(a, n));
    }
}
XOR Pairs are : 2

复杂度分析  

时间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。 访问数组中的元素需要O(1)时间。 因此,时间复杂度是线性的。

参见
在排序的旋转数组中搜索元素

空间复杂度

O(最大) 其中,Max是数组中所有元素中的最大元素。