وګوره چې ورکړل شوی صف یو له بل څخه د k فاصلو کې ورته عنصرونه لري


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon اویلارا د فراه تاريخي کلا وړیا چارج هیکرینک Snapchat سنیپډیل
پیشه هاش

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

وګوره چې ورکړل شوی صف یو له بل څخه د k فاصلو کې ورته عنصرونه لري

مثالونه

K = 3   arr[] = {1, 2, 3, 4, 5, 2, 1}
False
K = 2   arr[] = {3, 4, 3, 1, 1, 2, 6}
True

تشریح

موږ د دې ستونزې حل کولو لپاره دوه میتودونه لرو. ساده یو د دوه لوپونو چلول دي چیرې چې لومړی لوپ به هر عنصر د دویم لوپ 'انټر لوپ' لپاره د پیل عنصر په توګه غوره کړي. له هغې وروسته ، دوهم لوپ به د پیل عنصر د 'k' په حد کې دننه ټولو عناصرو سره پرتله کړي. مګر دا حل دومره اغیزناک ندی چې دا د O (k * n) وخت پیچلتیا اخلي.

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

د چیک کولو لپاره الګوریتم که چیرې ورکړل شوي صف یو له بل څخه د k فاصلو کې ورته عنصرونه لري

  1. لومړی ، خالي جوړ کړئ مخلوط ټکی په کوم کې چې موږ به د صف عناصر زیرمه کړو.
  2. د صف څخه ټول عناصر له کی from څخه ښیې ته وګرځوئ.
  3. وګورئ چې عنصر په هیش کې شتون لري که نه.
    • که دا هلته وي نو بیا "ریښتیا" ته راستون شئ.
    • نور هغه عنصر په هاش کې اضافه کړئ.
  4. بیا وروسته د ارار [ik] عنصر له هاش څخه لرې کړئ که چیرې 'I' لوی وي یا د 'k' سره مساوي وي.

 

موږ یو آرري [آرر] لرو چې پدې کې یو څه عنصر لرو او د ارزښت k چې هغه حد دی چې موږ پکې ورته نقلونه موندلو که شتون ولري نو لومړی به موږ د عناصرو ذخیره کولو لپاره هش سیټ وکاروو لومړی به موږ عناصر اضافه کړو. زموږ په هش کې صفونه یو له یو څخه ترتیب کړئ که عنصر لا دمخه په هش سیټ کې وي نو دا به بیرته راستن شي او پای ته ورسیږي نو دا به په دوامداره ډول په سیټ کې عنصر داخل کړي او له سیر څخه آر آر [ik] عنصر لرې کړي.

کوډ

C ++ کوډ چیک کولو لپاره چې آیا ورکړل شوی صف یو له بل څخه د k فاصلو کې ورته عنصرونه لري

#include<iostream>
#include<unordered_set>
using namespace std;

bool Check_Duplicates(int a[], int n, int k)
{

    unordered_set<int> D_set;

    for (int i = 0; i < n; i++)
    {
        if (D_set.find(a[i]) != D_set.end())
            return true;

        D_set.insert(a[i]);
        if (i >= k)
            D_set.erase(a[i-k]);
    }
    return false;
}

int main ()
{
    int a[] = {1, 2, 3, 4, 1};
    int k = 5;
    cout << ((Check_Duplicates(a, 5, k)) ? "Yes" : "No");
}
Yes

د جاوا کوډ چیک کولو لپاره چې ایا ورکړل شوی صف یو له بل څخه د k فاصلو کې ورته عنصرونه لري

import java.util.*;
class D_Class
{
    static boolean Check_Duplicates(int a[], int k)
    {

        HashSet<Integer> D_set = new HashSet<>();

        for (int i=0; i<a.length; i++)
        {
            if (D_set.contains(a[i]))
                return true;

            D_set.add(a[i]);
            if (i >= k)
                D_set.remove(a[i-k]);
        }
        return false;
    }

    public static void main (String[] args)
    {
        int a[] = {1, 2, 3, 4, 1};
        int k = 5;

        if (Check_Duplicates(a, k))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
Yes

د پیچلتیا تحلیل

د وخت پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی. د هش سیټ کارول په لاین وخت کې د ستونزې حل ته اجازه ورکوي. له هغه وخته چې د هش سیټ کارول د معلوماتو په اغیزمنه توګه د لټون ، حذف کولو او داخلولو وړتیا لوړوي.

د ځای پیچلتیا

سمه ده) هلته "K" په کړکۍ کې د عناصرو شمیر دی چې باید ورته وګوري.