ຊອກຫາອົງປະກອບທີ່ມີຢູ່ໃນແຖວ ທຳ ອິດແລະບໍ່ແມ່ນໃນອັນດັບສອງ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ຕິຊົມ ເດລີ ປັດໃຈ ສະ ເໜ່ Snapdeal Zoho
Array Hash

ບັນຫາ“ ຊອກຫາອົງປະກອບທີ່ມີຢູ່ໃນແຖວ ທຳ ອິດແລະບໍ່ແມ່ນໃນວິນາທີ” ລະບຸວ່າທ່ານໄດ້ຮັບສອງຢ່າງ ອາຄານ. ຂບວນປະກອບດ້ວຍທັງ ໝົດ integers. ທ່ານຕ້ອງຊອກຫາຕົວເລກທີ່ຈະບໍ່ຢູ່ໃນແຖວທີສອງແຕ່ປະຈຸບັນໃນແຖວ ທຳ ອິດ.

ຍົກຕົວຢ່າງ

ຊອກຫາອົງປະກອບທີ່ມີຢູ່ໃນແຖວ ທຳ ອິດແລະບໍ່ແມ່ນໃນອັນດັບສອງ

a [] = {2,4,3,1,5,6}
b [] = {2,1,5,6}
4 3
a [] ={4,2,6,8,9,5}
b [] ={9,3,2,6,8}
4

ລະບົບວິເຄາະ

  1. ປະກາດກ HashSet.
  2. ໃສ່ທຸກອົງປະກອບຂອງຂຂ [] ເຂົ້າໃນ HashSet.
  3. ໃນຂະນະທີ່ຂ້ອຍ <l1 (ຄວາມຍາວຂອງແຖວ a []).
    1. ຖ້າ HashSet ບໍ່ມີ array [i], ແລ້ວພິມ [i].

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ໃຫ້ແຖວຕົວເລກຄົບຖ້ວນແລະມີບັນຫາທີ່ຮຽກຮ້ອງໃຫ້ຊອກຫາຕົວເລກທີ່ມີຢູ່ໃນແຖວ ທຳ ອິດແລະບໍ່ແມ່ນໃນແຖວທີສອງ. ພວກເຮົາ ກຳ ລັງຈະໃຊ້ ແຮກ ໃນບັນຫານີ້. Hashing ຊ່ວຍໃຫ້ພວກເຮົາຊອກຫາວິທີແກ້ໄຂໃນທາງທີ່ມີປະສິດຕິພາບ.

ພວກເຮົາ ກຳ ລັງຈະເອົາຕົວເລກຂຂຂຂຂຂໃສ່ໃນ HashSet ແລະຫລັງຈາກໃສ່ ຈຳ ນວນທັງ ໝົດ ຂຂຂ []. ພວກເຮົາ ກຳ ລັງກ້າວໄປຂ້າງ ໜ້າ a [] ແລະ ກຳ ນົດແຕ່ລະສ່ວນຂອງແຕ່ລະເທື່ອແລະກວດເບິ່ງວ່າ HashSet ບໍ່ມີສ່ວນປະກອບນັ້ນບໍ. ຖ້າມັນບໍ່ມີສ່ວນປະກອບນັ້ນ, ພວກເຮົາ ກຳ ລັງຈະພິມອົງປະກອບສະເພາະນັ້ນຂອງອາເລ a [i] ແລະກວດເບິ່ງຕົວເລກອື່ນ.

ຂໍໃຫ້ເຮົາພິຈາລະນາຕົວຢ່າງແລະເຂົ້າໃຈເລື່ອງນີ້:

ແຖວ ທຳ ອິດແມ່ນ [] = a [] = {2,6,8,9,5,4}, b [] = {9,5,2,6,8}

ພວກເຮົາຕ້ອງໃສ່ທຸກອົງປະກອບຂອງ array b [] ເຂົ້າໃນ HashSet, ດັ່ງນັ້ນໃນ HashSet, ພວກເຮົາມີຄຸນຄ່າດັ່ງຕໍ່ໄປນີ້:

HashSet: {9,5,2,6,8} // ໂດຍພື້ນຖານຄ່າທັງ ໝົດ ຂອງ b [].

ພວກເຮົາຈະຂ້າມອາເລ a [] ແລະເອົາແຕ່ລະສ່ວນຂອງສ່ວນປະກອບຂອງມັນແລະກວດກາສະພາບການ.

i = 0, a [i] = 2

2 ແມ່ນຢູ່ໃນ HashSet, ດັ່ງນັ້ນມັນຈະບໍ່ພິມ.

i = 1, a [i] = 6

6 ແມ່ນຢູ່ໃນ HashSet, ອີກເທື່ອ ໜຶ່ງ ມັນຈະບໍ່ຖືກພິມອອກ.

i = 2, a [i] = 8

8 ແມ່ນຢູ່ໃນ HashSet, ມັນຈະບໍ່ຖືກພິມອອກ.

i = 3, a [i] = 9

9 ແມ່ນຢູ່ໃນ HashSet, ດັ່ງນັ້ນມັນຈະບໍ່ພິມ.

i = 4, a [i] = 5

5 ແມ່ນຢູ່ໃນ HashSet, ອີກເທື່ອ ໜຶ່ງ ມັນຈະບໍ່ຖືກພິມອອກ.

i = 5, a [i] = 4

4 ບໍ່ໄດ້ຢູ່ໃນ HashSet, ສະນັ້ນເວລານີ້ມັນຈະຖືກພິມ ໝາຍ ຄວາມວ່າມັນແມ່ນຕົວເລກທີ່ມີຢູ່ໃນແຖວ a [] ແຕ່ບໍ່ແມ່ນໃນຂຂ [] ເພາະວ່າໂດຍພື້ນຖານແລ້ວ HashSet ແມ່ນ clone ຂອງ array b [] ແລະຜົນຜະລິດຂອງພວກເຮົາຈະ ກາຍເປັນ '4'.

ລະຫັດ C ++ ເພື່ອຊອກຫາອົງປະກອບທີ່ມີຢູ່ໃນແຖວ ທຳ ອິດແລະບໍ່ແມ່ນໃນວິນາທີ

#include<unordered_set>
#include<iostream>
using namespace std;

void getMissingElement(int A[], int B[], int l1, int l2)
{
  unordered_set <int> myset;

  for (int i = 0; i < l2; i++)
    myset.insert(B[i]);

  for (int j = 0; j < l1; j++)
    if (myset.find(A[j]) == myset.end())
      cout << A[j] << " ";
}
int main()
{
    int a[] = { 9, 2, 3, 1, 4, 5 };
    int b[] = { 2, 4, 1, 9 };
  int l1 = sizeof(a) / sizeof(a[0]);
  int l2 = sizeof(b) / sizeof(b[0]);
  getMissingElement(a, b, l1, l2);
  return 0;
}
3 5

ລະຫັດ Java ເພື່ອຊອກຫາອົງປະກອບທີ່ມີຢູ່ໃນແຖວ ທຳ ອິດແລະບໍ່ແມ່ນໃນອັນດັບສອງ

import java.util.HashSet;
import java.util.Set;

class missingElement
{
    public static void getMissingElement(int A[], int B[])
    {
        int l1 = A.length;
        int l2 = B.length;

        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < l2; i++)
            set.add(B[i]);

        for (int i = 0; i < l1; i++)
            if (!set.contains(A[i]))
                System.out.print(A[i]+" ");
    }
    public static void main(String []args)
    {
        int a[] = { 9, 2, 3, 1, 4, 5 };
        int b[] = { 2, 4, 1, 9 };

        getMissingElement(a, b);
    }
}
3 5

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

ໂອ (N) ບ່ອນທີ່ "N" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນ array1. ເນື່ອງຈາກວ່າການໃຊ້ HashSet ສຳ ລັບການແຊກແລະການຄົ້ນຫາເຮັດໃຫ້ພວກເຮົາສາມາດ ດຳ ເນີນການເຫຼົ່ານີ້ໃນ O (1). ດັ່ງນັ້ນຄວາມສັບສົນຂອງເວລາແມ່ນເປັນເສັ້ນ.

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

ໂອ (N) ບ່ອນທີ່ "N" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນ array1. ນັບຕັ້ງແຕ່ພວກເຮົາ ກຳ ລັງເກັບຮັກສາອົງປະກອບຂອງແຖວທີສອງ. ດັ່ງນັ້ນພື້ນທີ່ທີ່ຕ້ອງການແມ່ນຄືກັນກັບຂະ ໜາດ ຂອງຂບວນທີສອງ.