ပထမ ဦး ဆုံးဒြပ်စင်တစ်ခုခင်းကျင်းအတွက် k ကြိမ်ဖြစ်ပေါ်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ ခရီးသွား PayU SAP Labs Teradata Wipro ရတနာ Zoho
အခင်းအကျင်း hash

နံပါတ် 'k' နဲ့ integer array တစ်ခုပေးထားတယ်။ အဆိုပါပြ “နာ "ပထမ ဦး ဆုံးဒြပ်စင်တစ်ခုခင်းကျင်းအတွက် k ကြိမ်ဖြစ်ပေါ်" ကခင်းကျင်းအတိအကျ k ကြိမ်ဖြစ်ပေါ်သောခင်းကျင်းအတွက်ပထမ ဦး ဆုံးဒြပ်စင်ထွက်ရှာရန်ကပြောပါတယ်။ k တွင်ဖြစ်ပေါ်သော array တွင် element မရှိပါက -1 သို့ပြန်သွားပါ။

နမူနာ

တစ် ဦး အကွာအဝေး၏ပျောက်ဆုံးနေဒြပ်စင်ရှာပါ

Arr[]={1,4,5,2,4,2,7},  k=2
4

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

ဤဥပမာတွင် k ကြိမ်ဖြစ်ပေါ်သော element နှစ်မျိုးရှိသည်။ ၄ နှင့် ၂ သည်အတိအကျ k အကြိမ်အရေအတွက်ရှိသည်။ သို့သော် ၄ သည် k ကြိမ်ဖြစ်သည်။ ဒါဆိုငါတို့ 4 ပြန်လာတယ်။

algorithm

  1. a) ကြေညာပါ HashMap.
  2. ခင်းကျင်းဖြတ်သန်း။
    • Array ၏ element တစ်ခု၏ကြိမ်နှုန်းကိုမြေပုံတွင်ရေတွက်။ သိမ်းထားပါ။
  3. ထပ်မံ၍ array ကိုထပ်မံစစ်ဆေးပြီး array element တစ်ခု၏ကြိမ်နှုန်းသည် k နှင့်ညီသည်ကိုစစ်ဆေးပါ။
    • အခြေအနေကကျေနပ်ပြီဆိုလျှင် element ကိုပြန်ပို့ပါ။

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

ငါတို့ကဲ့သို့ကျွန်ုပ်တို့၏ input ကိုတန်ဖိုးများရှိသည် ကိန်း အခင်းအကျင်း နှင့်တစ်ခုကိန်း k ။ ဒီပြstatementနာကကြေငြာချက်က k ကြိမ်အတိအကျပေါ်ပေါက်လာတဲ့ array ထဲမှာပထမဆုံး element ကိုရှာဖို့ပြောတယ်။ ဒီပြproblemနာကိုဖြေရှင်းဖို့ငါတို့သုံးမယ် တားဆီးခြင်း။ Hashing သည်ကျွန်ုပ်တို့၏အချိန်ရှုပ်ထွေးမှုကိုလျှော့ချနိုင်သည့်နည်းလမ်းဖြစ်သည်။ ကုန်ကျသည် အို (ဎ) အချိန်ရှုပ်ထွေး။

ကျွန်ုပ်တို့မြေပုံတွင်ဒြပ်စင်တစ်ခုစီ၏ကြိမ်နှုန်းကိုရေတွက်။ သိမ်းဆည်းလိမ့်မည်။ element တစ်ခုကို array ထဲမှာ 3 ကြိမ်ထည့်ပြီး၎င်းရဲ့ frequency ကို 3 အဖြစ်သတ်မှတ်တယ်။ ဤရည်ရွယ်ချက်အတွက်သော့နှင့်တန်ဖိုးများကိုသိမ်းဆည်းရန် HashMap ကိုအသုံးပြုနိုင်သည်။ ကျွန်ုပ်တို့သည် element များအားလုံးကိုသော့အဖြစ်နှင့်သူတို့၏ကြိမ်နှုန်းကို HashMap တွင်တန်ဖိုးများအဖြစ်သိမ်းဆည်းလိမ့်မည်။ ပြီးရင် loop တစ်ခုကိုသွားပြီး array တစ်ခုကိုဖြတ်သန်းပြီး element တစ်ခုစီကိုရွေးပြီးသူတို့ရဲ့ကြိမ်နှုန်းကိုစစ်ဆေးပါလိမ့်မယ်။ မည်သည့် element ၏ကြိမ်နှုန်းကို k နှင့်မတွေ့ပါကကျွန်ုပ်တို့သည်ထို element ကိုပြန်သွားပါမည်။ ကျနော်တို့ array ကိုဖြတ်သန်းနေကြသည်ကတည်းက element ကိုဖြစ်ပျက်မှု k နှင့်အတူတွေ့ရှိခဲ့လျှင်။ ထိုအခါကျိန်းသေ၎င်းသည် k ဖြစ်ပျက်မှု k မရှိသောပထမဆုံးဒြပ်စင်ဖြစ်လိမ့်မည်။

ဥပမာတစ်ခုကိုသုံးသပ်ကြည့်ကြစို့။

arr [] = {2,4,6,4,2,1,}, = = 2

ကျွန်ုပ်တို့သည် element များကိုသော့အဖြစ်သိမ်းဆည်းပြီးသူတို့၏ကြိမ်နှုန်းများကိုတန်ဖိုးများအဖြစ်မြေပုံထဲသို့သိုလှောင်ပါမည်။ ကျွန်ုပ်တို့၏မြေပုံကိုသိမ်းဆည်းပြီးနောက်အောက်ပါတန်ဖိုးများရှိလိမ့်မည်။

myMap={1:1, 2:2, 4:2, 6:1};

ကျနော်တို့ array element တစ်ခုစီကို 0th index ကနေစပြီးစစ်ကြည့်မယ်

i = 0,

တစ်ခုချင်းစီကိုခင်းကျင်း၏ကြိမ်နှုန်း [i] == k လျှင်

2 ၏ကြိမ်နှုန်းသည် 2 ဖြစ်သည်။ ၎င်းသည် k နှင့်လည်းအတူတူဖြစ်သည်။ ၎င်းသည်ပထမဆုံးအကြိမ်ဖြစ်ပျက်သည် k သည်မဖြစ်ပျက်မှုနှင့်အတူပထမဆုံးဖြစ်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် arr [i] ကိုပြန်ပို့ပြီးကျွန်ုပ်တို့၏ output သည် ၂ ဖြစ်သည်။

အကယ်၍ element တစ်ခု၏ကြိမ်နှုန်းသည် 'k' နှင့်မကိုက်ညီပါကကျွန်ုပ်တို့သည် -1 သို့ပြန်သွားပါမည်။

ကုဒ်

C ++ ကုဒ်ကိုပထမဆုံးအကြိမ် element k ကိုဖြစ်ပေါ်စေခြင်းဖြစ်သည်

#include<iostream>
#include <unordered_map>

using namespace std;

int firstElement(int arr[], int n, int k)
{
    unordered_map<int, int> freqMap;

    for (int i=0; i<n; i++)
        freqMap[arr[i]]++;

    for (int i=0; i<n; i++)
        if (freqMap[arr[i]] == k)
            return arr[i];

    return -1;
}
int main()
{
    int arr[] = {2,4,6,4,2,1,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << firstElement(arr, n, k);
    return 0;
}
2

Java element ကိုပထမဆုံးအကြိမ်အနေနဲ့ element တစ်ခုကို k ကြိမ်အကြိမ်ကြိမ်စစ်ခင်းကျင်းမှုတစ်ခုတွေ့ရှိရန်

import java.util.HashMap;

class firstKOccuringElement
{
    public static int getFirstElement(int arr[], int n, int k)
    {
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < n; i++)
        {
            int a = 0;
            if(freqMap.containsKey(arr[i]))
            {
                freqMap.put(arr[i], freqMap.get(arr[i])+1);
            }
            else
            {
                freqMap.put(arr[i], 1);
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (freqMap.get(arr[i]) == k)
            {
                return arr[i];
            }
        }
        return -1;
    }
    public static void main(String[] args)
    {
        int arr[] = {2,4,6,4,2,1,6};
        int n = arr.length;
        int k = 2;
        System.out.println(getFirstElement(arr, n, k));
    }
}
2

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (ဎ) ဘယ်မှာ “ n” သည် array ထဲရှိ element အရေအတွက်ဖြစ်သည်။ ဒီမှာ hashmap ကိုသုံးပြီးပြီဆိုရင် O (1) အချိန်မှာစစ်ဆင်ရေးတွေလုပ်နိုင်ပါပြီ။

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

အို (ဎ) ဘယ်မှာ “ n” သည် array ထဲရှိ element အရေအတွက်ဖြစ်သည်။ အဆိုးဆုံးအမှု၌အားလုံးသောဒြပ်စင်များဖြစ်ကြသည်။ ကျွန်ုပ်တို့သည် N element အားလုံးအားလုံးကိုမြေပုံတွင်သိုလှောင်ထားရမည်ဖြစ်ပြီး၎င်းသည် linear နေရာယူမည်။