هغه عناصر ومومئ کوم چې په لومړي صف کې شتون لري نه په ثانیه کې


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي اکولایټ دهلي حقیقت انځورونه سنیپډیل زو
پیشه هاش

ستونزه "هغه عناصر ومومئ کوم چې په لومړي صف کې شتون لري او په دویم کې ندي" په ګوته کوي چې تاسو ته دوه ورکړل شوي تیرونه. سریزونه ټول شامل دي ضمیمه. تاسو باید هغه شمیرې ومومئ کوم چې به په دوهم قطار کې شتون نلري مګر په لومړي صف کې شتون ولري.

بېلګه

هغه عناصر ومومئ کوم چې په لومړي صف کې شتون لري نه په ثانیه کې

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] یې چاپ کړه.

تشریح

موږ دوه بشپړ عريضې او د ستونزې بیان وړاندې کړی چې د هغه شمیره موندلو لپاره ترې پوښتل کیږي کوم چې په لومړي صف کې شتون لري نه په دوهم صف کې. موږ کارولو ته ځو ځورول پدې ستونزه کې. هشینګ موږ سره مرسته کوي چې موثره لاره د حل لاره ومومئ.

موږ به په هش سیټ کې د صفونو [[] شمیرې ځای په ځای کړو او وروسته د صفري ټول شمیر داخلولو وروسته []. موږ د صف له مخې ځو A [] او په یو وخت کې هر عنصر اخلو او وګورو چې ایا هش شیټ دا عنصر نلري. که چیرې دا عنصر ونه لري ، نو موږ به د ځانګړي برخې عنصر چاپ کړو [i] او د بلې شمیرې لپاره چک کوو.

راځئ چې یو مثال په پام کې ونیسو او پدې پوه شو:

لومړی صف یو دی [] = a [] = {2,6,8,9,5,4،9,5,2,6,8،XNUMX،XNUMX،XNUMX،XNUMX}، b [] = {XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

موږ باید د صفري [b] ټول عناصر په هش سیټ کې داخل کړو ، نو په هش سیټ کې موږ لاندې ارزښتونه لرو:

هش سیټ: {9,5,2,6,8،XNUMX،XNUMX،XNUMX،XNUMX} // اساسا د B ټول ارزښتونه [].

موږ به صف یو []] تیر کړو او د هغې هر عنصر واخلو او حالت به وګورو.

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 په هش سیټ کې ندي ، نو دا ځل به دا چاپ شي پدې معنی چې دا هغه شمیره ده چې په صف کې شتون لري a [] مګر په صف کې ندي [[] ځکه چې په اصل کې هیس سیټ د سرنی 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

د جاوا کوډ ترڅو عناصر ومومئ کوم چې په لومړي صف کې شتون لري او په دوهم کې ندي

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" په صف کې د عناصرو شمیر دی. ځکه چې د اضافې او لټون لپاره د هش سیټ کارول موږ ته اجازه راکوي چې دا عملیات په O (1) کې ترسره کړو. پدې توګه د وخت پیچلتیا لاهم ده.

د ځای پیچلتیا

O (N) هلته "N" په صف کې د عناصرو شمیر دی. ځکه چې موږ د دوهم صف عناصر ذخیره کوو. نو پدی توګه اړین ځای د دوهم سرنی د اندازې سره ورته دی.