Գտեք տարրեր, որոնք առկա են առաջին զանգվածում, և ոչ թե երկրորդում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Ակոլիտ Առաքում Փաստեր Ֆանատիկա Snapdeal Zoho
Դասավորություն Խանգարել

«Գտեք տարրեր, որոնք առկա են առաջին զանգվածում, և ոչ թե երկրորդում» խնդիրը ասում է, որ ձեզ տրվում է երկու զանգվածներ, Raանգվածները բաղկացած են բոլորից ամբողջական թվերը, Դուք պետք է պարզեք այն թվերը, որոնք ներկա չեն լինի երկրորդ զանգվածում, բայց առկա կլինեն առաջին զանգվածում:

Օրինակ

Գտեք տարրեր, որոնք առկա են առաջին զանգվածում, և ոչ թե երկրորդում

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]:

բացատրություն

Մենք տվել ենք երկու ամբողջ զանգված և խնդրի հայտարարություն, որը խնդրում է պարզել այն թիվը, որն առկա է առաջին զանգվածում, և ոչ թե երկրորդ զանգվածում: Մենք պատրաստվում ենք օգտագործել Հեշինգ այս խնդրի մեջ: Հեշինգը օգնում է մեզ արդյունավետ կերպով պարզել լուծումը:

Մենք պատրաստվում ենք զանգվածի 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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ) որտեղ «Ն» զանգվածում տարրերի քանակն է 1: Քանի որ HashSet- ը տեղադրելու և որոնելու համար օգտագործելը մեզ թույլ է տալիս կատարել այս գործողությունները O (1) -ում: Այսպիսով, ժամանակի բարդությունը գծային է:

Տիեզերական բարդություն

ՎՐԱ) որտեղ «Ն» զանգվածում տարրերի քանակն է 1: Քանի որ մենք պահում ենք երկրորդ զանգվածի տարրերը: Այսպիսով, պահանջվող տարածքը նույնն է, ինչ երկրորդ զանգվածի չափի: