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


Ниво на тешкотија Лесно
Често прашувано во Аколит Деливерија Факти Фанатици 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. Додека јас <l1 (должина на низа a []).
    1. Ако HashSet не содржи низа a [i], тогаш отпечатете [i].

Објаснување

Дадовме две интегрални низи и изјава за проблем што бара да се открие бројот што е присутен во првата низа, а не во втората низа. Е користиме Хашинг во овој проблем. Хашингот ни помага да го откриеме решението на ефикасен начин.

Toе ги ставиме броевите во низата b [] во HashSet и откако ќе го вметнеме целиот број на низата b []. Toе ја пресечеме низата 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 [].

Traе ја поминеме низата 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

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

Временска комплексност

НА) каде „Н“ е бројот на елементи во низата1. Бидејќи користењето на HashSet за вметнување и пребарување ни овозможува да ги извршиме овие операции во О (1). Така, временската сложеност е линеарна.

Комплексноста на просторот

НА) каде „Н“ е бројот на елементи во низата1. Бидејќи ги зачувуваме елементите на втората низа. Така, потребниот простор е ист како оној на големината на втората низа.