چڪاس ڪريو ته جيڪڏهن ڏنل قطار ۾ هڪ ٻئي کان فاصلو تي نقل وارا عنصر شامل هجن


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon اوولارا قلعي مفت چارج ھيڪر رِڪن Snapchat اسپيڊل
ڪيريو هاش

مسئلو ”چيڪ ڪريو جيڪڏهن ڪو ترتيب ڏنل هڪ ٻئي کان فاصلو ۾ نقل وارا عنصر شامل آهن“ بيان ڪري ٿو ته اسان کي ڪ جي حد ۾ ڏنل اڻ ترتيب واري ترتيب ۾ نقل جي چڪاس ڪرڻي آهي. هتي k جي قيمت ڏنل ڏنل ترتيب کان نن isي آهي.

چڪاس ڪريو ته جيڪڏهن ڏنل قطار ۾ هڪ ٻئي کان فاصلو تي نقل وارا عنصر شامل هجن

مثال

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

وضاحت

اسان وٽ هن مسئلي کي حل ڪرڻ جا ٻه طريقا آهن. سمجهه وارو هڪ هڪ آهي ٻه لوپ هلائڻ جنهن ۾ پهريون لوپ هر عنصر کي هڪ چونڊ عنصر ابتدائي عنصر طور ٻئي لوپ جي اندر واري لوپ کي چونڊيندو. ان کان پوءِ ، ٻئي لوپ شروع ٿيندڙ عنصر کي ”ڪ“ جي حد اندر سمورن عنصرن سان تشبيهه ڏيندو. پر اهو حل ڪارائتو ناهي ته اهو O (k * n) جي وقت جي پيچيدگين وٺندو آهي.

پر اسان وٽ هڪ وڌيڪ موثر طريقو آهي جيڪو انهي مسئلي کي حل ڪري سگهي ٿو اي (ن) وقت جي پيچيدگي سڏيو وڃي ٿو چُڪڻ. هشنگ جي طريقي ۾ ، اسين صف جي سڀني عنصرن کي پار ڪري ڇڏينداسين ۽ جاچ ڪنداسين ته اهو عنصر ان ۾ موجود آهي يا نه. جيڪڏهن عنصر اتي موجود آهي ته اسان واپس ٿينداسين ’صحيح‘. ٻي صورت ۾ اسين هن کي هاش ۾ شامل ڪندا ۽ اعشار [ik] عنصر کي هش مان هٽايو جيڪڏهن 'i' کان وڏو يا 'k' جي برابر آهي.

الگورٿم چيڪ ڪرڻ لاءِ ته ڏنل ڏنل قطار ۾ هڪ ٻئي کان فاصلن ۾ نقل وارا عنصر شامل آهن

  1. پهرين ، خالي ٺاهيو هيش سيٽ جنهن ۾ اسان صف جا عنصر محفوظ ڪنداسين.
  2. کاٻي کان سا rightي تائين صف جا سڀئي عنصر ڳوليو.
  3. چيڪ ڪريو ته عنصر هيش ۾ موجود آهي يا نه.
    • جيڪڏھن اھو اتي ھجي پوءِ “سچو” موٽي وڃ.
    • ايلس اهو عنصر هش ۾ شامل ڪريو.
  4. ان کان پوءِ هيش مان arr [ik] عنصر ختم ڪريو جيڪڏهن ‘I’ وڏو يا برابر آهي ‘k’.

 

اسان وٽ ارئر آهي arr =] انهي ۾ ڪجھ عنصر ۽ قدر ڪي جيڪا حد آهي جنهن ۾ اسان کي ٻٻر لڳائڻا پوندا جيڪڏهن ڪو آهي ته هيش سيٽ استعمال ڪندس پهرين عناصر ان کي رکڻ لاءِ اسان شامل ڪنداسين اسان جي هيش ۾ صف هڪ هڪ ڪري جيڪڏهن عنصر اڳ ۾ ئي هش سيٽ ۾ آهي ته پوءِ اهو سچو موٽي ويندو ۽ لوپ کي ٽوڙيو ٻئي ۾ اهو لڳاتار سيٽ ۾ عناصر داخل ڪندو ۽ سيٽ تان arr [ik] عنصر کي هٽائيندو.

ڪوڊ

C ++ ڪوڊ اهو پڙتال ڪريو ته ڇا ڏنل سيٽ ۾ هڪ ٻئي کان فاصلن ۾ نقل وارا عنصر موجود آهن

#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

جاوا ڪوڊ اهو چيڪ ڪرڻ لاءِ ته ڏنل لائين ۾ هڪ ٻئي کان فاصلن ۾ نقل وارا عنصر آهن

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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي. هش سيٽ استعمال ڪرڻ سان مسئلو کي حل ڪرڻ جي سڌي وقت ۾ اجازت ڏئي ٿو. جئين هيش سيٽ استعمال ڪرڻ کان ڊيٽا کي ڳولا ، حذف ڪرڻ ۽ داخل ڪرڻ جي صلاحيت کي وڌائيندو آهي.

خلائي پيچيدگي

اي (ڪ) جتي ”ڪي“ ڇا ونڊو ۾ عناصر جو تعداد آھي جيڪي ڏسڻ جي ضرورت آھي.