Намерете елементи, които присъстват в първия масив, а не във втория


Ниво на трудност Лесно
Често задавани в Аколит Делхейвъри FactSet Фанатиците Snapdeal Zoho
Array Хашиш

Проблемът „Намери елементи, които присъстват в първия масив, а не във втория“ гласи, че са ви дадени два масиви. Масивите се състоят от всички числа. Трябва да откриете числата, които няма да присъстват във втория масив, но присъстват в първия масив.

Пример

Намерете елементи, които присъстват в първия масив, а не във втория

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], отпечатайте a [i].

Обяснение

Дадохме два целочислени масива и декларация за проблем, която иска да открие числото, което присъства в първия масив, а не във втория масив. Ще използваме хеширане в този проблем. Хеширането ни помага да намерим решението по ефективен начин.

Ще поставим числата на масива 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

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

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

НА) където "Н" е броят на елементите в масива1. Тъй като използването на HashSet за вмъкване и търсене ни позволява да извършваме тези операции в O (1). По този начин сложността на времето е линейна.

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

НА) където "Н" е броят на елементите в масива1. Тъй като съхраняваме елементите от втория масив. По този начин необходимото пространство е същото като това на размера на втория масив.