لومړی عنصر په یو صف کې د k وخت پیښ کیږي


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon هیک پیرو یو د SAP لابراتوارونه Teradata (Wipro) یاترا زو
پیشه هاش

موږ د 'k' شمیره او د عدد سیر ورکړئ. ستونزه "لومړي عنصر په یو صف کې د k بار پیښیږي" وايي په صف کې د لومړي عنصر موندلو لپاره چې په صف کې په سمه توګه k بار پیښیږي. که په صف کې کوم عنصر شتون ونلري چې د k وختونه پیښ شي نو بیرته راستنیدنه -1.

بېلګه

د اندازې ورک شوي عناصر ومومئ

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

تشریح

پدې مثال کې ، دوه عناصر شتون لري چې د k وختونه پیښیږي. 4 او 2 دقیق شمیر k وختونه شتون لري ، مګر 4 لومړی دی چې د k وختونه پیښیږي. نو موږ بیرته راستنیدو 4.

الګوریتم

  1. اعلامیه a هش میپ.
  2. سرنی ترې تېر کړئ.
    • په نخشه کې د صف د هر عنصر فریکونسۍ حساب او زیرمه کړئ.
  3. یوځل بیا صف ځوړند کړئ او وګورئ چې د هر صف عنصر فریکوینسي د k سره مساوي ده.
    • که حالت مطمئن وي ، نو عنصر بیرته راشئ.

تشریح

موږ لکه څنګه چې زموږ ننوتلي ارزښتونه لرو ضمیمه سور او یو عدد ک. د ستونزې بیان غوښتنه کوي چې په یو صف کې د لومړي عنصر موندلو لپاره چې دقیق k وختونه پیښیږي. د دې ستونزې حل کولو لپاره ، موږ به وکاروو ځورول. ځړول هغه احتمالي لار ده چې له لارې موږ کولی شو زموږ د وخت پیچلتیا کمه کړو. دا لګښت لري اې (N) د وخت پیچلتیا.

موږ به زموږ په نقشه کې د هر عنصر فریکوینسي شمیره او ذخیره کړو. فرض کړئ چې یو عنصر په صف کې 3 ځله راځي موږ د دې عنصر سره د دې فریکونسۍ 3 په توګه ټاکي. هش میپ د دې مقصد لپاره د کیلو او ارزښتونو ذخیره کولو لپاره کارول کیدی شي. موږ به ټول عناصر د کیچونو او د دوی فریکونسیو په توګه په هش میپ کې د ارزښتونو په توګه زیرمه کړو. بیا به موږ یو لاپ چلوو او یو صف راولیږو او هر عنصر به یې غوره کوو او د دوی فریکوینسي به یې وګورو. که د کوم عنصر فریکوینسي د k سره مساوي وموندل شي ، نو بیا به موږ هغه عنصر بیرته راشي. له هغه وخته چې موږ په صف کې تیریږو ، نو که چیرې عنصر د پیښې k وختونو سره وموندل شي. بیا په یقین سره چې دا به د لومړي ځل لپاره د k واقعاتو هیڅ عنصر وي.

راځئ چې یوه بېلګه په نظر کې ونیسو:

تیر [] = {2,4,6,4,2,1،2،XNUMX،XNUMX،XNUMX،XNUMX،}، k = XNUMX

موږ به نقشه کې د ارزښتونو په توګه عناصر د کیلي او د دوی فریکونسۍ ذخیره کړو ، زموږ د نقشه ذخیره کولو وروسته لاندې ارزښتونه به وي:

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

موږ به د هر صف عنصر وګورو ، د 0 له شاخص څخه به پیل کوو چې موږ به د صف څخه تیر شو

i = 0 ،

که چیرې د هر صف فریکونسۍ [i] == k:

د 2 فریکونسۍ 2 ده 2 ، کوم چې د k سره مساوي هم دي دا هغه عنصر دی چې د k پیښو نه سره لومړی راځي ، نو موږ آر آر بیرته راوړو [i] او زموږ محصول به XNUMX وي.

په هغه حالت کې که چیرې د عنصر کوم فریکوینسي د 'k' سره مطابقت ونه لري ، نو موږ به بیرته راشي .1.

کوډ

C ++ کوډ چې په لومړي سر کې د 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

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

د ځای پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی. په خورا بد حالت کې کله چې ټول عناصر توپیر ولري. موږ به ټول N عناصر په نقشه کې زیرمه کړو کوم چې به خطي ځای ونیسي.