两组的不重叠和


难度级别 易得奖学金
经常问 ol石 亚马逊 远足 库利扎 Pinterest Snapdeal 新思 Teradata数据
排列 哈希

问题陈述

问题“两组的不重叠和”表明给您两个数组作为输入值,大小为n的arrA []和arrB []。 同样,这两个阵列分别具有不同的元素和一些共同的元素。 您的任务是找出所有非常见元素的总和。

使用案列

arrA[] = {1,3,4,5,2}
arrB[] = {2,4,6,7,8}
30

说明

上面一组数组中的不同元素是1、3、5、6、7和8。

总和为= 1+ 3 + 5 + 6 + 7 +8 = 30。

两组的不重叠和

 

arrA[]={1,3,4,5,2}
arrB[]={3,4,1,5,7}
9

说明

所有元素都是通用的,因此输出将为0。

算法

  1. 声明一个 地图.
  2. 遍历 排列 当i <n(数组的长度)时。
    1. 计算阵列中两个元素的频率并将其存储到映射中。
  3. 将totalSum设置为0。
  4. 遍历地图。
    1. 检查地图的元素值是否等于1。
      1. 如果为true,则继续将所有元素添加到totalSum中。
  5. 返回totalSum。

 说明

我们给出了两个元素共同的输入数组。 问题陈述要求找出两个数组中所有不常见的元素的总和。 为此,我们将使用 散列. 哈希图 与键和值一起使用,它将具有键,并且该值与键相关联。 因此,它可以一起工作。 我们将声明一个哈希图,并在单个映射中,我们将两个数组的元素及其频率存储在映射中。

使用案列

让我们考虑一个示例:arrA [] = {1,3,4,5,2},arrB [] = {2,4,6,7,8}

由于两个数组的大小均相同。 在遍历两个数组时,我们只需要遍历一次,就可以完成元素和频率的遍历。 之后,我们的地图将具有以下值。

地图:{1:1,2:2,3:1,4:2,5:1,6:1,7:1,8:1}。

将变量totalSum设置为0后,我们需要遍历地图以获得所有非公共元素的总和。 我们将检查条件,如果任何元素的频率为1,我们将选择该元素并将其与totalSum相加并存储到totalSum中。

totalSum = 0,

  • 地图的第一个元素“ 1”具有1个频率,并将其添加到totalSum => totalSum +键= 0 +1 = 1。
  • Map的第二个元素“ 2”的频率为2,因此我们不会使用该键,因为它在两个数组中都是通用的。
  • 地图的第一个元素“ 3”具有1个频率,并将其添加到totalSum => totalSum +键= 1 +3 = 4。
  • Map的第二个元素“ 4”的频率为2,因此我们不会使用该键,因为它在两个数组中都是通用的。
  • 地图的第一个元素“ 5”具有1个频率,我们将其添加到totalSum => totalSum + key = 4 +5 = 9。

类似地,我们将在totalSum中添加6、7和8,因为所有频率的值都为1。 因此它将变为1+ 3 + 5 + 6 + 7 +8 = 30。

输出:30

代码

C ++中两组不重叠总和的实现

#include <unordered_map>
#include<iostream>

using namespace std;

int findSum(int arrA[], int arrB[], int n)
{
    unordered_map<int, int> map;
    for (int i = 0; i < n; i++)
    {
        map[arrA[i]]++;
        map[arrB[i]]++;
    }
    int totalSum = 0;
    for (auto sel: map)
        if (sel.second == 1)
            totalSum += sel.first;

    return totalSum;
}
int main()
{
    int arrA[] = { 5, 1, 10, 4, 7 };
    int arrB[] = { 1, 6, 7, 8, 2 };
    int l = sizeof(arrA) / sizeof(arrA[0]);
    cout << findSum(arrA, arrB, l);
    return 0;
}
35

用Java实现两个集合的不重叠总和

import java.util.HashMap;
import java.util.Map;

class nonOverlappingSum
{
    public static int findSum(int[] A, int[] B, int n)
    {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++)
        {
            if (map.containsKey(A[i]))
                map.put(A[i], map.get(A[i]) + 1);
            else
                map.put(A[i], 1);

            if (map.containsKey(B[i]))
                map.put(B[i], map.get(B[i]) + 1);
            else
                map.put(B[i], 1);
        }
        int totalSum = 0;
        for (Map.Entry entry : map.entrySet())
        {
            if (Integer.parseInt((entry.getValue()).toString()) == 1)
                totalSum += Integer.parseInt((entry.getKey()).toString());
        }
        return totalSum;

    }
    public static void main(String args[])
    {
        int arrA[] = { 5, 1, 10, 4, 7 };
        int arrB[] = { 1, 6, 7, 8, 2 };
        int l = arrA.length;
        System.out.println(findSum(arrA, arrB, l));
    }
}
35

复杂度分析

时间复杂度

O(N) 哪里 “ n” 是数组的长度。 因为我们使用了哈希图,所以所有搜索,删除和更新操作都是在O(1)时间复杂度下完成的。 因此,我们能够实现线性时间复杂度。

空间复杂度

O(N) 哪里 “ n” 是数组的长度。 需要空间将两个数组的元素存储到map中。