XNUMXセットの重複しない合計


難易度 簡単に
よく聞かれる アコライト Amazon (アマゾン) ハイキング クリザ Pinterest Snapdeal シノプシス Teradataの
配列 ハッシング

問題文

問題「XNUMXつのセットの重複しない合計」は、同じサイズnのarrA []およびarrB []として入力値としてXNUMXつの配列が与えられることを示しています。 また、両方の配列には、個別の要素といくつかの共通要素があります。 あなたの仕事は、すべての一般的でない要素の合計を見つけることです。

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です。

XNUMXセットの重複しない合計

 

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を返します。

 説明

一部の要素が共通であるXNUMXつの入力配列を指定しました。 問題ステートメントは、珍しい両方の配列のすべての要素の合計を見つけるように求めています。 このために、私たちは使用するつもりです ハッシュ. ハッシュマップ キーと値で機能し、キーがあり、値はキーに関連付けられています。 だからそれは一緒に動作します。 ハッシュマップを宣言し、単一のマップで、両方の配列の要素をそれらの頻度とともにマップに格納します。

例を考えてみましょう:arrA [] = {1,3,4,5,2}、arrB [] = {2,4,6,7,8}

両方の配列が同じサイズnであるため。 両方の配列をトラバースしている間、XNUMX回トラバースする必要があります。その中で、要素と周波数を処理します。 その後、マップの値は次のようになります。

マップ:{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 + key = 0 +1 = 1に追加します。
  • マップの2番目の要素「2」の頻度はXNUMXであるため、両方の配列で共通であるため、そのキーは使用しません。
  • マップの最初の要素「3」には1つの頻度があり、それをtotalSum => totalSum + key = 1 +3 = 4に追加します。
  • マップの4番目の要素「2」の頻度はXNUMXであるため、両方の配列で共通であるため、そのキーは使用しません。
  • マップの最初の要素「5」には1つの頻度があり、totalSum => totalSum + key = 4 +5 = 9に追加します。

同様に、頻度として値が6であるため、totalSumに7、8、および1を追加します。 したがって、1 + 3 + 5 + 6 + 7 +8 = 30になります。

出力:30

コード

XNUMXセットの重複しない合計のための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

XNUMXセットの重複しない合計のための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) where 「n」 は配列の長さです。 ハッシュマップを使用したため、検索、削除、更新のすべての操作はO(1)時間計算量で実行されています。 したがって、線形時間計算量を達成することができました。

スペースの複雑さ

O(N) where 「n」 は配列の長さです。 両方の配列の要素をマップに格納するには、スペースが必要です。