ผลรวมสองชุดที่ไม่ทับซ้อนกัน  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคโคไลท์ อเมซอน ธุดงค์ คูลิซา Pinterest Snapdeal Synopsys Teradata
แถว hashing

คำชี้แจงปัญหา  

ปัญหา“ ผลรวมสองชุดที่ไม่ทับซ้อนกัน” ระบุว่าคุณได้รับสองอาร์เรย์เป็นค่าอินพุตเป็น arrA [] และ arrB [] ที่มีขนาดเท่ากัน นอกจากนี้อาร์เรย์ทั้งสองยังมีองค์ประกอบที่แตกต่างกันแยกกันและองค์ประกอบทั่วไปบางส่วน งานของคุณคือการหาผลรวมขององค์ประกอบที่ไม่ใช่องค์ประกอบทั่วไปทั้งหมด

ตัวอย่าง  

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. ส่งคืน totalSum

 คำอธิบาย

เราได้ให้อาร์เรย์อินพุตสองอาร์เรย์ซึ่งองค์ประกอบบางอย่างเป็นเรื่องปกติ คำสั่งปัญหาขอให้ค้นหาผลรวมขององค์ประกอบทั้งหมดของอาร์เรย์ทั้งสองซึ่งผิดปกติ สำหรับสิ่งนี้เราจะใช้ hashing. แฮชแมป ทำงานกับคีย์และค่าโดยจะมีคีย์และค่าจะเชื่อมโยงกับคีย์ ดังนั้นจึงทำงานร่วมกัน เราจะประกาศแฮชแมปและในแผนที่เดียวเราจะจัดเก็บองค์ประกอบของอาร์เรย์ทั้งสองลงในแผนที่พร้อมความถี่

ดูสิ่งนี้ด้วย
บันทึกการเข้าเรียนของนักเรียน 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 + key = 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 (n) ที่ไหน “ n” คือความยาวของอาร์เรย์ เนื่องจากเราใช้แฮชแมปการดำเนินการทั้งหมดในการค้นหาการลบและการอัปเดตกำลังดำเนินการในความซับซ้อนของเวลา O (1) ดังนั้นเราจึงสามารถบรรลุความซับซ้อนของเวลาเชิงเส้นได้

ดูสิ่งนี้ด้วย
ค้นหาหมายเลข K สูงสุด (หรือบ่อยที่สุด) ในสตรีม

ความซับซ้อนของอวกาศ

O (n) ที่ไหน “ n” คือความยาวของอาร์เรย์ ต้องใช้ช่องว่างในการจัดเก็บองค์ประกอบของอาร์เรย์ทั้งสองลงในแผนที่