ຊຸດທີ່ບໍ່ຊ້ອນກັນຂອງສອງຊຸດ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Amazon hike ກຸລະກິ Pinterest Snapdeal Synopsys Teradata
Array ແຮກ

ຖະແຫຼງການບັນຫາ

ບັນຫາ“ ຜົນລວມທີ່ບໍ່ຊ້ ຳ ຊ້ອນຂອງສອງຊຸດ” ລະບຸວ່າທ່ານໄດ້ຮັບສອງອາຄານເປັນມູນຄ່າການປ້ອນຂໍ້ມູນເປັນ 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. Traverse ໄດ້ array ໃນຂະນະທີ່ຂ້ອຍ <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.

totalSum = 0,

  • ອົງປະກອບ ທຳ ອິດຂອງແຜນທີ່ '1' ມີ 1 ຄວາມຖີ່ແລະເພີ່ມມັນໃສ່ totalSum => totalSum + key = 0 +1 = 1.
  • ອົງປະກອບທີສອງຂອງແຜນທີ່ມີຄວາມຖີ່ 2 ດັ່ງນັ້ນພວກເຮົາຈະບໍ່ເອົາກຸນແຈນັ້ນເພາະມັນເປັນເລື່ອງ ທຳ ມະດາໃນທັງສອງແຖວ.
  • ອົງປະກອບ ທຳ ອິດຂອງແຜນທີ່ '3' ມີ 1 ຄວາມຖີ່ແລະເພີ່ມມັນໃສ່ totalSum => totalSum + key = 1 +3 = 4.
  • ອົງປະກອບທີສອງຂອງແຜນທີ່ມີຄວາມຖີ່ 4 ດັ່ງນັ້ນພວກເຮົາຈະບໍ່ເອົາກຸນແຈນັ້ນເພາະມັນເປັນເລື່ອງ ທຳ ມະດາໃນທັງສອງແຖວ.
  • ອົງປະກອບ ທຳ ອິດຂອງແຜນທີ່ '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

ການຈັດຕັ້ງປະຕິບັດຢູ່ໃນເກາະຊາວາ ສຳ ລັບການສັງລວມແບບບໍ່ຊ້ອນກັນຂອງສອງຊຸດ

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" ແມ່ນຄວາມຍາວຂອງຂບວນ. ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ ນຳ ໃຊ້ hashmap ທຸກໆການ ດຳ ເນີນງານຂອງການຄົ້ນຫາ, ການລຶບແລະການປັບປຸງ ກຳ ລັງ ດຳ ເນີນຢູ່ໃນ O (1) ເວລາທີ່ສັບສົນ. ດັ່ງນັ້ນພວກເຮົາສາມາດບັນລຸຄວາມສັບສົນທີ່ໃຊ້ເວລາເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ບ່ອນທີ່ "n" ແມ່ນຄວາມຍາວຂອງຂບວນ. ຕ້ອງມີພື້ນທີ່ເກັບຮັກສາອົງປະກອບຂອງອາຄານທັງສອງເຂົ້າໃນແຜນທີ່.