Збир на непреклопување на два сета


Ниво на тешкотија Лесно
Често прашувано во Аколит Амазон Крстоносните Кулиза Pinterest Snapdeal Synopsys Teradata
Низа Хашинг

Изјава за проблем

Проблемот „Непреклопувачки збир на две множества“ вели дека ви се дадени две низи како влезни вредности како arRA [] и arRB [] со иста големина n. Исто така, обете низи имаат посебни елементи поединечно и некои заеднички елементи. Ваша задача е да ја дознаете вкупната сума на сите необични елементи.

пример

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. Помина низ низа додека јас <n (должина на низата).
    1. Пресметајте ги и зачувајте ги фреквенциите на двата елементи на низата во картата.
  3. Постави totalSum на 0.
  4. Поминете ја картата.
    1. Проверете дали картата има вредност на елементот еднаква на 1.
      1. Ако е точно, тогаш продолжете да ги додавате сите елементи во totalSum.
  5. Врати го вкупниот збир.

 Објаснување

Дадовме две влезни низи во кои некои од елементите се вообичаени. Изјавата за проблемот бара да се открие вкупниот збир на сите елементи на двете низи кои се невообичаени. За ова, ние ќе користиме хашинг. Хашмап работи со клуч и вредности, ќе има клучеви и вредноста е поврзана со клучот. Така, работи заедно. Declaе прогласиме хашмап и во единствена мапа, ќе ги зачуваме елементите од обете низи во картата со нивните фреквенции.

пример

Да разгледаме пример: 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 + клуч = 0 +1 = 1.
  • Вториот елемент на картата „2“ има фреквенција 2, затоа нема да го земеме тој клуч бидејќи е вообичаен и во двете низи.
  • Првиот елемент на картата „3“ има 1 фреквенција и додајте го на totalSum => totalSum + клуч = 1 +3 = 4.
  • Вториот елемент на картата „4“ има фреквенција 2, затоа нема да го земеме тој клуч бидејќи е вообичаен и во двете низи.
  • Првиот елемент на картата „5“ има 1 фреквенција, го додаваме на totalSum => totalSum + клуч = 4 +5 = 9.

Слично на тоа, ќе додадеме 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

Имплементација во Јава за непреклопувачки збир од два сета

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 (1) сложеност во времето. Така, успеавме да постигнеме линеарна сложеност во времето.

Комплексноста на просторот

Тој) каде „Н“ е должината на низата. Потребен е простор за складирање на елементите од двете низи во картата.