Непокриваща се сума от два комплекта


Ниво на трудност Лесно
Често задавани в Аколит Амазонка Екскурзия Кулиза Pinterest Snapdeal Synopsys Терадата
Array хеширане

Декларация за проблема

Проблемът „Непокриваща се сума на два набора“ гласи, че са ви дадени два масива като входни стойности като 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. Прекоси масив докато i <n (дължина на масива).
    1. Пребройте и съхранете честотите на двата елемента на масива в картата.
  3. Задайте totalSum на 0.
  4. Прекосете картата.
    1. Проверете дали картата със стойност на елемента е равна на 1.
      1. Ако е вярно, продължете да добавяте всички елементи в totalSum.
  5. Връщане totalSum.

 Обяснение

Дадохме два входни масива, в които някои от елементите са общи. Изложението на проблема изисква да се открие общата сума на всички елементи на двата масива, които са необичайни. За това ще използваме хеширане. Hashmap работи с ключ и стойности, той ще има ключове и стойността е свързана с ключа. Така че работи заедно. Ще декларираме хеш-карта и в една карта ще съхраним елементи от двата масива в картата с техните честоти.

Пример

Нека разгледаме пример: 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.

обща сума = 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 в totalSum, защото всички имат стойността 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 (1). Така успяхме да постигнем линейна сложност във времето.

Сложност на пространството

О (п) където "н" е дължината на масива. Необходимо е място за съхраняване на елементите от двата масива в карта.