በመጀመሪያ ድርድር ውስጥ የሚገኙ እና በሁለተኛ ደረጃ የማይገኙ አባሎችን ይፈልጉ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የተከማቸ አቅርቦት ፋርስት አፍቃሪዎች Snapdeal ቮሆ
ሰልፍ ሃሽ

ችግሩ “በመጀመሪያ ድርድር ውስጥ የሚገኙ እና በሰከንድ ውስጥ የሌሉ ንጥረ ነገሮችን ይፈልጉ” የሚለው ሁለት እንደተሰጠ ይገልጻል ድርድሮች. ዝግጅቶች ሁሉንም ያካተቱ ናቸው ኢንቲጀሮች. በሁለተኛው ድርድር ውስጥ የማይገኙ ግን በመጀመሪያው ድርድር ውስጥ የሚገኙትን ቁጥሮች መፈለግ አለብዎት።

ለምሳሌ

በመጀመሪያ ድርድር ውስጥ የሚገኙ እና በሁለተኛ ደረጃ የማይገኙ አባሎችን ይፈልጉ

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. ያውጅ ሀ ሃሽሴት.
  2. ሁሉንም የድርጅት ለ [ሀ] አካላት ወደ HashSet ያስገቡ።
  3. I <l1 እያለ (የአንድ ድርድር ርዝመት a [])
    1. HashSet ድርድር አንድ [i] ከሌለው ፣ ከዚያ አንድ [i] ን ያትሙ።

ማስረጃ

በሁለተኛው ድርድር ውስጥ ሳይሆን በመጀመሪያው ድርድር ላይ የሚገኘውን ቁጥር ለማወቅ የሚጠይቅ ሁለት የኢቲጀር ድርድር እና የችግር መግለጫ ሰጥተናል ፡፡ ልንጠቀምበት ነው ሃምሽንግ በዚህ ችግር ውስጥ ፡፡ ሀሺንግ መፍትሄውን በብቃት ለመፈለግ ይረዳናል ፡፡

የድርጅት ለ [ቁጥሮችን] በ HashSet ውስጥ እናደርጋለን እና ሁሉንም የድርጅት ቁጥር ከገባን በኋላ ለ []። እኛ አንድን አንድ ላይ እናቋርጣለን እና እያንዳንዱን ንጥረ ነገር በአንድ ጊዜ እንወስዳለን እና ሃሽሴት ያንን ንጥረ ነገር ከሌለው እንፈትሻለን ፡፡ ያ አካል ከሌለው ያንን የተወሰነ የ “i” ድርድርን ማተም እና ሌላ ቁጥር እንፈትሻለን።

እስቲ አንድ ምሳሌን እንመልከት እና ይህንን እንረዳ ፡፡

የመጀመሪያው ድርድር አንድ [] = a [] = {2,6,8,9,5,4} ነው ፣ ለ [] = {9,5,2,6,8}

ሁሉንም የ “[b]] ን ክፍሎች ወደ ሃሽሴት ማስገባት አለብን ፣ ስለዚህ በሃሽሴት ውስጥ የሚከተሉትን እሴቶች አሉን

HashSet: {9,5,2,6,8} // በመሠረቱ ሁሉም የ [[] እሴቶች።

ድርድርን አንድ [] በማለፍ እያንዳንዱን ንጥረ ነገሮችን ወስደን ሁኔታውን እንፈትሻለን።

i = 0 ፣ አንድ [i] = 2

2 በ HashSet ውስጥ ነው ፣ ስለሆነም አይታተምም።

i = 1 ፣ አንድ [i] = 6

6 በ HashSet ውስጥ ነው ፣ እንደገና አይታተምም።

i = 2 ፣ አንድ [i] = 8

8 በ HashSet ውስጥ ነው ፣ አይታተምም።

i = 3 ፣ አንድ [i] = 9

9 በ HashSet ውስጥ ነው ፣ ስለሆነም አይታተምም።

i = 4 ፣ አንድ [i] = 5

5 በ HashSet ውስጥ ነው ፣ እንደገና አይታተምም።

i = 5 ፣ አንድ [i] = 4

4 በ HashSet ውስጥ የለም ፣ ስለዚህ በዚህ ጊዜ ይታተማል ማለት በአንድ ድርድር ውስጥ የሚገኝ ቁጥር ነው [] ግን በድርድር ውስጥ አይደለም ለ [] ምክንያቱም በመሠረቱ ሀሽሴት የደርጅት ለ ነው [እና] ውጤታችን '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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) የት "N" በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት 1 ነው። ምክንያቱም ለማስገባት እና ለመፈለግ HashSet ን በመጠቀም እነዚህን (ኦ) ውስጥ ለማከናወን ያስችሉናል ፡፡ ስለዚህ የጊዜ ውስብስብነት መስመራዊ ነው።

የቦታ ውስብስብነት

ኦ (ኤን) የት "N" በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት 1 ነው። የሁለተኛውን ድርድር አካላት ስለምናስቀምጥ። ስለዚህ የሚፈለገው ቦታ ከሁለተኛው ድርድር መጠን ጋር ተመሳሳይ ነው።