Биринчи массивде болгон элементтерди табыңыз, экинчисинде жок


Кыйынчылык деңгээли жеңил
Көп суралган Accolite Delhivery Factset динчилдер Snapdeal Zoho
согуштук тизме таштанды

"Биринчи массивде бар элементтерди табыңыз" деген маселеде экиге берилгениңизди билдирет Arrays. Массивдер баарынан турат бүтүн. Экинчи массивде жок, бирок биринчи массивде орун алган сандарды табышыңыз керек.

мисал

Биринчи массивде болгон элементтерди табыңыз, экинчисинде жок

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

Algorithm

  1. Декларация a HashSet.
  2. B [] массивинин бардык элементтерин HashSet ичине киргизиңиз.
  3. While i <l1 (a [] массивинин узундугу).
    1. Эгер HashSetте [i] массиви жок болсо, анда [i] басып чыгарыңыз.

түшүндүрүү

Биз эки бүтүндөй массивди жана экинчи массивде эмес, биринчи массивде болгон номурду табууну сураган көйгөйдү чыгардык. Биз колдоно турган болдук Hashing бул көйгөйдө. Хэшинг бизге натыйжалуу жол менен чечим табууга жардам берет.

Массив 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те жок, демек, бул жолу ал басылып чыгат, бул ал [] массивинде бар, бирок 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. Экинчи массивдин элементтерин сактап жаткандыктан. Ошентип, талап кылынган боштук экинчи массивдин көлөмү менен бирдей.