İkincidə yox, birinci massivdə olan elementləri tapın

“Birinci sırada olmayan elementləri tapın” problemi sizə ikisinin verildiyini bildirir seriallar. Diziler bütün bunlardan ibarətdir tamsayılar. İkinci massivdə olmayacaq, ancaq birinci cərgədə mövcud olan rəqəmləri öyrənməlisiniz.

misal

Pin

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

Alqoritm

1. Bəyan edin a HashSet.
2. B [] massivinin bütün elementlərini HashSet-ə daxil edin.
3. While i <l1 (a [] massivinin uzunluğu).
   1. HashSet-də bir [i] massivi yoxdursa, onda [i] yazdırın.

Izahat

İki tam sıra və ikinci massivdə yox, birinci massivdə olan ədədi öyrənməyi xahiş edən bir problem ifadəsi verdik. İstifadə edəcəyik Hashing bu problemdə. Hashing, həll yolunu səmərəli bir şəkildə tapmağa kömək edir.

B [] ədədlərini bir HashSet-ə qoyacağıq və bütün sıra [b]] daxil etdikdən sonra. A [] cərgəsini keçəcəyik və hər bir elementi bir anda götürərək HashSet-də bu elementin olub-olmadığını yoxlayacağıq. Əgər o elementə sahib deyilsə, biz [a] massivinin həmin elementini çap edəcəyik və başqa bir nömrəni yoxlayacağıq.

Bir nümunəni nəzərdən keçirək və bunu başa düşək:

Birinci sıra a [] = a [] = {2,6,8,9,5,4}, b [] = {9,5,2,6,8}

B [] massivinin bütün elementlərini HashSet-ə daxil etməliyik, buna görə HashSet-də aşağıdakı dəyərlərə sahibik:

HashSet: {9,5,2,6,8} // əsasən b [] dəyərləri.

A [] dizisini keçib hər bir elementini götürüb vəziyyəti yoxlayacağıq.

i = 0, a [i] = 2

2 HashSet-də olduğu üçün çap olunmayacaq.

i = 1, a [i] = 6

6 HashSet-də, yenə də çap olunmayacaq.

i = 2, a [i] = 8

8 HashSet-də, çap olunmayacaq.

i = 3, a [i] = 9

9 HashSet-də olduğu üçün çap olunmayacaq.

i = 4, a [i] = 5

5 HashSet-də, yenə də çap olunmayacaq.

i = 5, a [i] = 4

4, HashSet-də deyil, bu dəfə çap ediləcəyi bir a [] massivində mövcud olan rəqəmdir, ancaq b [] massivində deyil, çünki HashSet əsasən b [] massivinin klonudur və bizim çıxışımız '4' ol.

C ++ kodu ikinci massivdə mövcud olan elementləri tapmaq üçün

#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

İkincidə deyil, birinci massivdə olan elementləri tapmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N) hara "N" massivdəki elementlərin sayıdır1. Çünki əlavə və axtarış üçün HashSet-dən istifadə etmək bu əməliyyatları O (1) -də yerinə yetirməyə imkan verir. Beləliklə, zamanın mürəkkəbliyi doğrudur.

Kosmik Mürəkkəblik

O (N) hara "N" massivdəki elementlərin sayıdır1. İkinci sıra elementlərini saxladığımız üçün. Beləliklə, tələb olunan yer ikinci massivin ölçüsü ilə eynidır.