Найдите элементы, которые присутствуют в первом массиве, а не во втором  


Сложный уровень Легко
Часто спрашивают в Акколит Деливери Набор фактов Фанатики Snapdeal Zoho
массив 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. Пока i <l1 (длина массива a []).
    1. Если HashSet не содержит массива a [i], выведите a [i].

объяснение

Мы дали два целочисленных массива и формулировку задачи, которая просит узнать число, которое присутствует в первом массиве, а не во втором массиве. Мы собираемся использовать хеширования в этой проблеме. Хеширование помогает нам эффективно найти решение.

Мы собираемся поместить массив чисел b [] в HashSet и после вставки всех номеров массива b []. Мы собираемся пройти по массиву a [] и взять каждый элемент за раз и проверить, не содержит ли HashSet этот элемент. Если у него нет этого элемента, мы собираемся распечатать этот конкретный элемент массива a [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 [].

Мы пройдем по массиву a [], возьмем каждый из его элементов и проверим условие.

я = 0, а [я] = 2

2 находится в HashSet, поэтому он не будет печататься.

я = 1, а [я] = 6

6 находится в HashSet, опять же, он не будет распечатан.

я = 2, а [я] = 8

8 находится в HashSet, он не будет распечатан.

я = 3, а [я] = 9

9 находится в HashSet, поэтому он не будет печататься.

я = 4, а [я] = 5

5 находится в HashSet, опять же, он не будет распечатан.

я = 5, а [я] = 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

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

Сложность времени

НА) в котором "N", - количество элементов в массиве1. Потому что использование HashSet для вставки и поиска позволяет нам выполнять эти операции за O (1). Таким образом, временная сложность линейна.

Смотрите также
Сравнение строк по частоте поиска наименьшего символа Leetcode Решение

Космическая сложность

НА) в котором "N", - количество элементов в массиве1. Поскольку мы храним элементы второго массива. Таким образом, необходимое пространство такое же, как и размер второго массива.