두 세트의 겹치지 않는 합계-TutorialCup

차례

문제 정책

"두 세트의 겹치지 않는 합계"문제는 동일한 크기 n의 arrA [] 및 arrB []와 같은 입력 값으로 두 개의 배열이 제공된다는 것을 나타냅니다. 또한 두 배열에는 개별 요소와 일부 공통 요소가 있습니다. 당신의 임무는 모든 비 공통 요소의 총합을 찾는 것입니다.

예

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

설명

위의 배열 집합에서 고유 한 요소는 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}

설명

모든 요소는 공통이므로 출력은 0이됩니다.

암호알고리즘

선언 지도.
횡단 정렬 while i <n (배열의 길이).
1. 두 배열 요소의 빈도를 계산하고 맵에 저장합니다.
totalSum을 0으로 설정하십시오.
지도를 횡단합니다.
1. 요소의 값이 1 인지도가 있는지 확인합니다.
  1. true이면 모든 요소를 totalSum에 계속 추가하십시오.
totalSum을 반환합니다.

설명

일부 요소가 공통된 두 개의 입력 배열을 제공했습니다. 문제 설명은 흔하지 않은 두 배열의 모든 요소의 총합을 알아 내도록 요청합니다. 이를 위해 우리는 해싱. 해시 맵 키와 값으로 작동하며 키를 가지며 값은 키와 연결됩니다. 그래서 함께 작동합니다. 해시 맵을 선언하고 단일 맵에서 두 배열의 요소를 주파수와 함께 맵에 저장합니다.

예

예를 들어 보겠습니다. arrA [] = {1,3,4,5,2}, arrB [] = {2,4,6,7,8}

두 배열 모두 동일한 크기 n이기 때문에. 두 배열을 모두 순회하는 동안 한 번만 순회하면됩니다. 그 안에서 요소와 주파수를 다룰 것입니다. 그 후 맵은 다음과 같은 값을 갖게됩니다.

지도 : {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에 추가합니다.
Map의 두 번째 요소 '2'에는 주파수 2가 있으므로 두 배열 모두에서 공통이기 때문에 해당 키를 사용하지 않습니다.
맵의 첫 번째 요소 '3'은 1 개의 빈도를 가지며 totalSum => totalSum + key = 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;
}

두 세트의 겹치지 않는 합계를위한 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));
    }
}

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 길이입니다. 해시 맵을 사용했기 때문에 검색, 삭제 및 업데이트의 모든 작업이 O (1) 시간 복잡도로 수행됩니다. 따라서 우리는 선형 시간 복잡성을 달성 할 수있었습니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 길이입니다. 두 배열의 요소를 맵에 저장하려면 공간이 필요합니다.

Twitter Facebook 링크드 인 버퍼 레딧 텀블러