Екінші жиында емес, бірінші жиымда болатын элементтерді табыңыз


Күрделілік дәрежесі оңай
Жиі кіреді Акколит Дели Factset Фанатика Шапшаң Зохо
Array Hash

«Екінші жиында емес, бірінші массивтегі элементтерді табыңыз» деген есеп сізге екі берілгенін айтады массивтер. Массивтер барлығынан тұрады бүтін сандар. Сіз екінші жиымда жоқ, бірақ бірінші жиымда болатын сандарды білуіңіз керек.

мысал

Екінші жиында емес, бірінші жиымда болатын элементтерді табыңыз

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. While i <l1 (а [] жиымының ұзындығы).
    1. Егер HashSet құрамында [i] жиымы болмаса, онда [i] басып шығарыңыз.

Түсіндіру

Біз екі бүтін массив пен екінші массивте емес, бірінші массивте болатын санды анықтайтын есептер шығардық. Біз қолданамыз Хэш бұл мәселеде. Хэштеу бізге шешімді тиімді жолмен табуға көмектеседі.

B [] сандарын HashSet ішіне және b [] жиымының барлық санын енгізгеннен кейін орналастырамыз. Біз [] массивінен өтіп, әр элементті бір уақытта алып, HashSet құрамында бұл элементтің жоқтығын тексереміз. Егер ондай элемент болмаса, біз [i] жиымының сол элементін басып шығарамыз және басқа нөмірді тексереміз.

Мысалды қарастырып, мынаны түсінейік:

Бірінші жиым a [] = a [] = {2,6,8,9,5,4}, b [] = {9,5,2,6,8}

B [] жиымының барлық элементтерін HashSet ішіне кірістіруіміз керек, сондықтан HashSet-те келесі мәндер бар:

HashSet: {9,5,2,6,8} // негізінен b [] мәндері.

Біз [[] массивін айналып өтіп, оның элементтерінің әрқайсысын аламыз және шартты тексереміз.

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

Күрделілікті талдау

Уақыттың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны1. HashSet-ті енгізу және іздеу үшін пайдалану бұл әрекеттерді O (1) -те орындауға мүмкіндік береді. Осылайша уақыттың күрделілігі сызықтық болып табылады.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны1. Біз екінші массивтің элементтерін сақтап жатқандықтан. Сонымен, екінші массивтің өлшемімен бірдей орын қажет.