మొదటి శ్రేణిలో ఉన్న అంశాలను కనుగొనండి మరియు రెండవది కాదు


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అకోలైట్ Delhivery ఫాక్ట్‌సెట్ ఇష్టపడేవారిని స్నాప్డీల్ జోహో
అర్రే హాష్

“మొదటి శ్రేణిలో ఉన్న అంశాలను కనుగొనండి మరియు రెండవది కాదు” అనే సమస్య మీకు రెండు ఇవ్వబడింది శ్రేణుల. శ్రేణులు అన్నింటినీ కలిగి ఉంటాయి పూర్ణాంకాల. మీరు రెండవ శ్రేణిలో ఉండకపోయినా మొదటి శ్రేణిలో ఉన్న సంఖ్యలను కనుగొనాలి.

ఉదాహరణ

మొదటి శ్రేణిలో ఉన్న అంశాలను కనుగొనండి మరియు రెండవది కాదు

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. ప్రకటించండి a హాష్‌సెట్.
  2. శ్రేణి b [] యొక్క అన్ని అంశాలను హాష్‌సెట్‌లోకి చొప్పించండి.
  3. నేను <l1 అయితే (శ్రేణి యొక్క పొడవు a []).
    1. హాష్‌సెట్‌లో శ్రేణి [i] ను కలిగి ఉండకపోతే, అప్పుడు [i] ను ముద్రించండి.

వివరణ

మేము రెండు పూర్ణాంక శ్రేణులను ఇచ్చాము మరియు మొదటి శ్రేణిలో ఉన్న సంఖ్యను రెండవ శ్రేణిలో కాకుండా కనుగొనమని అడిగే సమస్య ప్రకటన. మేము ఉపయోగించబోతున్నాం హ్యాషింగ్ ఈ సమస్యలో. హాషింగ్ మాకు పరిష్కారాన్ని సమర్థవంతంగా తెలుసుకోవడానికి సహాయపడుతుంది.

మేము శ్రేణి b [] సంఖ్యలను హాష్‌సెట్‌లో ఉంచబోతున్నాము మరియు శ్రేణి b యొక్క అన్ని సంఖ్యలను చేర్చిన తరువాత. మేము శ్రేణి [] ను దాటబోతున్నాము మరియు ప్రతి మూలకాన్ని ఒకేసారి తీసుకుంటాము మరియు హాష్‌సెట్‌లో ఆ మూలకం ఉందా అని తనిఖీ చేస్తాము. దీనికి ఆ మూలకం లేకపోతే, మేము శ్రేణి యొక్క నిర్దిష్ట మూలకాన్ని [i] ప్రింట్ చేయబోతున్నాము మరియు మరొక సంఖ్య కోసం తనిఖీ చేస్తాము.

ఒక ఉదాహరణను పరిశీలిద్దాం మరియు దీనిని అర్థం చేసుకుందాం:

మొదటి శ్రేణి ఒక [] = a [] = {2,6,8,9,5,4}, బి [] = {9,5,2,6,8}

మేము శ్రేణి b [] యొక్క అన్ని అంశాలను హాష్‌సెట్‌లోకి చేర్చాలి, కాబట్టి హాష్‌సెట్‌లో, మనకు ఈ క్రింది విలువలు ఉన్నాయి:

హాష్‌సెట్: {9,5,2,6,8} // ప్రాథమికంగా బి యొక్క అన్ని విలువలు [].

మేము శ్రేణిని [] దాటి, దానిలోని ప్రతి మూలకాలను తీసుకొని పరిస్థితిని తనిఖీ చేస్తాము.

i = 0, a [i] = 2

2 హాష్‌సెట్‌లో ఉంది, కాబట్టి ఇది ముద్రించదు.

i = 1, a [i] = 6

6 హాష్‌సెట్‌లో ఉంది, మళ్ళీ అది ముద్రించబడదు.

i = 2, a [i] = 8

8 హాష్‌సెట్‌లో ఉంది, ఇది ముద్రించబడదు.

i = 3, a [i] = 9

9 హాష్‌సెట్‌లో ఉంది, కాబట్టి ఇది ముద్రించదు.

i = 4, a [i] = 5

5 హాష్‌సెట్‌లో ఉంది, మళ్ళీ అది ముద్రించబడదు.

i = 5, a [i] = 4

4 హాష్‌సెట్‌లో లేదు, కాబట్టి ఈసారి అది ముద్రించబడుతుంది అంటే ఇది శ్రేణిలో ఉన్న సంఖ్య [] కాని శ్రేణి బి [] లో లేదు ఎందుకంటే ప్రాథమికంగా హాష్‌సెట్ శ్రేణి బి యొక్క క్లోన్ [] మరియు మా అవుట్పుట్ అవుతుంది '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

మొదటి శ్రేణిలో మరియు రెండవది లేని అంశాలను కనుగొనడానికి జావా కోడ్

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 లోని మూలకాల సంఖ్య. ఎందుకంటే చొప్పించడం మరియు శోధించడం కోసం హాష్‌సెట్‌ను ఉపయోగించడం O (1) లో ఈ కార్యకలాపాలను నిర్వహించడానికి అనుమతిస్తుంది. అందువలన సమయం సంక్లిష్టత సరళంగా ఉంటుంది.

అంతరిక్ష సంక్లిష్టత

పై) (ఇక్కడ  “ఎన్” శ్రేణి 1 లోని మూలకాల సంఖ్య. మేము రెండవ శ్రేణి యొక్క అంశాలను నిల్వ చేస్తున్నాము కాబట్టి. అందువల్ల అవసరమైన స్థలం రెండవ శ్రేణి యొక్క పరిమాణానికి సమానం.