מצא אלמנטים שנמצאים במערך הראשון ולא בשני


רמת קושי קַל
נשאל לעתים קרובות נאמן מסירה סט עובדות קנאות Snapdeal Zoho
מערך בליל

הבעיה "מצא אלמנטים שנמצאים במערך הראשון ולא בשני" קובעת שאתה מקבל שניים מערכים. מערכים מורכבים מכל מספרים שלמים. עליכם לברר את המספרים אשר לא יהיו במערך השני אלא במערך הראשון.

דוגמה

מצא אלמנטים שנמצאים במערך הראשון ולא בשני

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. הכנס את כל האלמנטים של מערך b [] ל- HashSet.
  3. ואילו i <l1 (אורך מערך a []).
    1. אם HashSet אינו מכיל מערך a [i], הדפס [i].

הסבר

נתנו שני מערכים שלמים והצהרת בעיה המבקשת לברר את המספר הקיים במערך הראשון ולא במערך השני. אנחנו הולכים להשתמש חבטות בבעיה זו. Hashing עוזר לנו לגלות את הפתרון בצורה יעילה.

אנו נכניס את מערכי b [] המספרים ל- HashSet ולאחר הכנסת כל מספר מערך b []. אנו הולכים לחצות את מערך a [] ולקחת כל אלמנט בכל פעם ולבדוק אם HashSet אינו מכיל את האלמנט הזה. אם אין בו אלמנט זה, אנו נדפיס את אותו אלמנט מסוים של מערך a [i] ונבדוק מספר אחר.

הבה נבחן דוגמה ונבין זאת:

המערך הראשון הוא [] = a [] = {2,6,8,9,5,4}, b [] = {9,5,2,6,8}

עלינו להכניס את כל האלמנטים של מערך 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 [] אך לא במערך b [] מכיוון שבעצם HashSet הוא השיבוט של מערך 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" הוא מספר האלמנטים במערך 1. מכיוון שהשימוש ב- HashSet לצורך הכנסה וחיפוש מאפשר לנו לבצע פעולות אלה ב- O (1). לפיכך מורכבות הזמן היא לינארית.

מורכבות בחלל

עַל) איפה "N" הוא מספר האלמנטים במערך 1. מכיוון שאנו מאחסנים את האלמנטים של המערך השני. לפיכך השטח הנדרש זהה לזה של גודל המערך השני.