Пронађите елементе који су присутни у првом низу, а не у другом  


Ниво тешкоће Лако
Често питани у Аццолите Делхивери Фацтсет Фанатици Снапдеал Зохо
Ред Хасх

Проблем „Пронађи елементе који су присутни у првом низу, а не у другом“ наводи да су вам дата два низови. Низови се састоје од свих интегерс. Морате открити бројеве који неће бити у другом низу, али ће бити у првом низу.

Пример  

Пронађите елементе који су присутни у првом низу, а не у другом

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. Изјавите а ХасхСет.
  2. Уметните све елементе низа б [] у ХасхСет.
  3. Док је и <л1 (дужина низа а []).
    1. Ако ХасхСет не садржи низ а [и], одштампајте [и].

Објашњење

Дали смо два целобројна низа и исказ проблема који тражи да се сазна број који је присутан у првом, а не у другом низу. Користићемо Хасхинг у овом проблему. Хасхинг нам помаже да ефикасно пронађемо решење.

Ставићемо бројеве низа б [] у ХасхСет и након убацивања сав број низа б []. Прећи ћемо низом [] и узимајући сваки елемент истовремено и проверити да ли ХасхСет не садржи тај елемент. Ако нема тај елемент, исписаћемо тај одређени елемент низа а [и] и потражити други број.

Размотримо пример и схватимо ово:

Види такође
Бројање индексних парова са једнаким елементима у низу

Први низ је а [] = а [] = {2,6,8,9,5,4}, б [] = {9,5,2,6,8}

Морамо уметнути све елементе низа б [] у ХасхСет, тако да у ХасхСет-у имамо следеће вредности:

ХасхСет: {9,5,2,6,8} // у основи све вредности б [].

Прећи ћемо низ а [] и узети сваки његов елемент и проверити стање.

и = 0, а [и] = 2

2 је у ХасхСет-у, па се неће штампати.

и = 1, а [и] = 6

6 је у ХасхСет-у, опет се неће штампати.

и = 2, а [и] = 8

8 је у ХасхСет-у, неће се штампати.

и = 3, а [и] = 9

9 је у ХасхСет-у, па се неће штампати.

и = 4, а [и] = 5

5 је у ХасхСет-у, опет се неће штампати.

и = 5, а [и] = 4

4 није у ХасхСету, па ће овај пут бити одштампан, значи да је то број који је присутан у низу а [], али не и у низу б [] јер је у основи ХасхСет клон низа б [] и наш излаз ће постаните '4'.

Ц ++ код за проналажење елемената који су присутни у првом низу, а не у другом  

#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

Јава код за проналажење елемената који су присутни у првом, а не у другом низу  

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

Анализа сложености  

Сложеност времена

НА) где "Н" је број елемената у низу1. Јер коришћење ХасхСет-а за уметање и претраживање омогућава нам да ове операције извршимо у О (1). Стога је временска сложеност линеарна.

Види такође
Упоредите жице по фреквенцији најмањег решења са леетцоде-ом

Сложеност простора

НА) где "Н" је број елемената у низу1. Пошто чувамо елементе другог низа. Стога је потребан простор исти као и величина другог низа.