ორი ნაკრების გადაფარვითი ჯამი  


Რთული ტური Easy
ხშირად ეკითხებიან თანამოსაყრელი Amazon ლაშქრობა კულიზა Pinterest Snapdeal ანოტაცია Teradata
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. დააბრუნე ჯამი

 განმარტება

ჩვენ მივეცით ორი შეყვანის მასივი, რომელშიც ზოგიერთი ელემენტი საერთოა. პრობლემის დებულება ითხოვს, რომ გაირკვეს ორივე მასივის ყველა ელემენტის საერთო ჯამი, რომელიც იშვიათია. ამისათვის ჩვენ ვაპირებთ გამოვიყენოთ ჰასინგი. ჰაშმაპი მუშაობს გასაღებით და მნიშვნელობებით, მას ექნება გასაღებები და მნიშვნელობა ასოცირდება გასაღებთან. ასე რომ, ის ერთად მუშაობს. ჩვენ გამოვაცხადებთ ჰეშმაპს და ერთ რუქაზე ვაპირებთ ორივე მასივის ელემენტების შენახვას რუკაზე მათი სიხშირეებით.

იხილეთ ასევე
სტუდენტთა დასწრების ჩანაწერი I Leetcode Solution

მაგალითი

განვიხილოთ მაგალითი: 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.
  • რუქის მეორე ელემენტს '2' აქვს სიხშირე 2, ამიტომ ამ კლავიშს არ ავიღებთ, რადგან ის ორივე მასივშია გავრცელებული.
  • რუკის პირველ ელემენტს '3' აქვს 1 სიხშირე და დაამატე მას totalSum => totalSum + key = 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 (n) სადაც "ნ" არის მასივის სიგრძე. რადგან ჩვენ გამოვიყენეთ ჰეშმაპი, ძიების, წაშლისა და განახლების ყველა ოპერაცია ხორციელდება O (1) დროის სირთულეში. ამრიგად, ჩვენ შევძელით ხაზოვანი დროის სირთულის მიღწევა.

იხილეთ ასევე
იპოვნეთ ყველაზე K (ან ყველაზე ხშირად) რიცხვები ნაკადში

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის სიგრძე. საჭიროა სივრცე მასივის ელემენტების რუქაზე შესანახად.