Element တွေကိုပထမ ဦး ဆုံးခင်းကျင်းပြသထားပြီးဒုတိယနေရာမှာမတွေ့ပါ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Accolite ဒေလီ အချက်အလက် ဝါသနာရှင်များ Snapdeal Zoho
အခင်းအကျင်း hash

ပြ “နာ က“ ဒုတိယ element မှာမဟုတ်ဘဲ first array ထဲမှာတွေ့ရတဲ့ element တွေကိုရှာပါ” ဆိုတဲ့ပြproblemနာကခင်ဗျားကိုနှစ်ခုပေးထားသည် Array များ။ Array များအားလုံးပါဝင်သည် ကိန်း။ ဒုတိယခင်းကျင်းမှုတွင်မပါ ၀ င်ရမည့်နံပါတ်များကိုသင်ရှာဖွေရမည်။

နမူနာ

Element တွေကိုပထမ ဦး ဆုံးခင်းကျင်းပြသထားပြီးဒုတိယနေရာမှာမတွေ့ပါ

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. array b [] များအားလုံးကို HashSet ထဲသို့ထည့်ပါ။
  3. ဈ <l1 (တစ်ခုခင်းကျင်း၏အရှည်တစ် []) <နေစဉ်။
    1. HashSet တွင် [i] တွင်မပါ ၀ င်ပါက [i] ကို print ထုတ်ပါ။

ရှင်းလင်းချက်

ကျနော်တို့ကိန်းဂဏန်းနှစ်မျိုးနဲ့ဒုတိယခင်းကျင်းထဲမှာမဟုတ်ဘဲပထမခင်းကျင်းပြသတဲ့နံပါတ်ကိုရှာဖို့တောင်းတဲ့ပြstatementနာကြေညာချက်တစ်ခုပေးထားတယ်။ ငါတို့သုံးမယ် တားဆီးခြင်း ဒီပြproblemနာမှာ။ Hashing သည်ကျွန်ုပ်တို့အားဖြေရှင်းနည်းကိုထိရောက်သောနည်းဖြင့်ရှာဖွေရန်ကူညီသည်။

Array b [] နံပါတ်များကို HashSet တွင်ထည့်ပြီး array b အားလုံးနံပါတ်ကိုထည့်ပြီးနောက်။ ကျွန်ုပ်တို့သည် array တစ်ခုကိုဖြတ်သန်းသွားမည်ဖြစ်ပြီး၊ တစ်ခုချင်းစီကိုတစ်ကြိမ်လျှင်ယူပြီး HashSet တွင်ထိုဒြပ်စင်မပါရှိမရှိစစ်ဆေးပါလိမ့်မည်။ အကယ်၍ ၎င်းတွင်ထိုဒြပ်စင်မရှိလျှင်၎င်းအထူးပြုခင်းကျင်းသည့် [a] array element ကိုပုံနှိပ်။ အခြားနံပါတ်ကိုစစ်ဆေးပါမည်။

ဥပမာတစ်ခုကိုလေ့လာပြီးဤအရာကိုနားလည်ကြပါစို့။

ပထမ ဦး ဆုံးခင်းကျင်းသည် [] = a [] = {2,6,8,9,5,4}, b [] = {9,5,2,6,8}

ကျွန်ုပ်တို့သည် array b [] ၏ element အားလုံးကို HashSet ထဲသို့ထည့်ရမည်ဖြစ်သည်။ HashSet တွင်အောက်ပါတန်ဖိုးများရှိသည်။

HashSet: {9,5,2,6,8} // အခြေခံအားဖြင့်ခ၏တန်ဖိုးအားလုံး [] ။

Array [] ကိုဖြတ်ပြီး၎င်းရဲ့အစိတ်အပိုင်းတစ်ခုစီကိုယူပြီးအခြေအနေကိုစစ်ဆေးပါမည်။

ကိုယ့် = 0 တစ် ဦး [ဈ] = 2

2 သည် HashSet တွင်တည်ရှိသောကြောင့်၎င်းကိုပုံနှိပ်ထုတ်ဝေမည်မဟုတ်ပါ။

ကိုယ့် = 1 တစ် ဦး [ဈ] = 6

6 သည် HashSet တွင်တည်ရှိပြီး၎င်းကိုပုံနှိပ်ထုတ်ဝေမည်မဟုတ်ပါ။

ကိုယ့် = 2 တစ် ဦး [ဈ] = 8

8 ဟာ HashSet ထဲမှာပါ။ ပုံနှိပ်တော့မှာမဟုတ်ပါဘူး။

ကိုယ့် = 3 တစ် ဦး [ဈ] = 9

9 သည် HashSet တွင်တည်ရှိသောကြောင့်၎င်းကိုပုံနှိပ်ထုတ်ဝေမည်မဟုတ်ပါ။

ကိုယ့် = 4 တစ် ဦး [ဈ] = 5

5 သည် HashSet တွင်တည်ရှိပြီး၎င်းကိုပုံနှိပ်ထုတ်ဝေမည်မဟုတ်ပါ။

ကိုယ့် = 5 တစ် ဦး [ဈ] = 4

4 သည် HashSet တွင်မရှိပါ၊ ဤတစ်ကြိမ်တွင်ပုံနှိပ်ထုတ်ဝေမည်ဖြစ်သည်။ ဆိုလိုသည်မှာ၎င်းသည် array တစ်ခုအတွင်းရှိ [] သည်နံပါတ် b ဖြစ်သည်။ ဆိုလိုသည်မှာအခြေခံအားဖြင့် HashSet သည် array b [] ၏ပုံသဏ္isာန်ဖြစ်သောကြောင့်ကျွန်ုပ်တို့၏ output မှာမူ။ '4' ဖြစ်လာသည်။

C ++ ကုဒ်ကိုရှာရန် element များကိုပထမ ဦး ဆုံးခင်းကျင်းပြသထားသော်လည်းဒုတိယနေရာတွင်မဟုတ်ပါ

#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 code ကိုရှာရန် element များကိုပထမအကြိမ်တွင်မဟုတ်ဘဲဒုတိယနေရာတွင်ရှိသည်

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) ဘယ်မှာ "N" အဆိုပါ array1 အတွက်ဒြပ်စင်များ၏နံပါတ်ဖြစ်ပါတယ်။ အကြောင်းမှာသွင်းခြင်းနှင့်ရှာဖွေခြင်းအတွက် HashSet ကိုအသုံးပြုခြင်းသည်ကျွန်ုပ်တို့အား O (1) တွင်ဤလုပ်ဆောင်မှုများပြုလုပ်ရန်ခွင့်ပြုထားသောကြောင့်ဖြစ်သည်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (N) ဘယ်မှာ "N" အဆိုပါ array1 အတွက်ဒြပ်စင်များ၏နံပါတ်ဖြစ်ပါတယ်။ ကျနော်တို့ဒုတိယခင်းကျင်း၏ဒြပ်စင်သိုလှောင်နေကြသည်ကတည်းက။ ထို့ကြောင့်လိုအပ်သောနေရာသည်ဒုတိယခင်းကျင်း၏အရွယ်နှင့်တူညီသည်။