عدد کی صف میں پہلا اعادہ عنصر تلاش کریں


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایمیزون فانٹکس میک مائیکروسافٹ اوریکل
لڑی ہیکنگ

مسئلہ یہ بیان

ایک میں دوہرانے والا پہلا عنصر تلاش کریں صف انٹریجرس کی پریشانی میں بتایا گیا ہے کہ آپ کو انٹیجر کی صف دی جاتی ہے۔ یہ صف سے پہلے دہرانے والے عنصر کا پتہ لگانے اور اس نمبر کو پرنٹ کرنے کے لئے کہتا ہے۔

مثال کے طور پر

arr[] = {2,6,9,3,1,9,1}
9

وضاحت: دیئے گئے صف میں دو اعداد ہیں جو دہرا رہے ہیں لیکن پہلی بار دہانی 9 ہے۔

arr[] = {1,4,7,0,2,5}
No repeating number.

وضاحت: دیئے گئے صف میں کوئی دہرانے والا نمبر نہیں ہے۔

پہلا اعادہ کردار تلاش کرنے کیلئے الگورتھم

1. Set flag to -1.
2. Declare a Set.
3. Start traversing the array from the right to left.
    1. If the number is repeating then update the value of flag to the index of the current array element.
    2. Else, insert the each array’s element into the declared set.
4. Check if flag value is still -1, then we have found no repeating element.
5. Else print flag index position of array.

وضاحت

عدد کی صف میں پہلا اعادہ عنصر تلاش کریں

 

ہم نے عدد کا ایک صف دیا ہے ، ہم نے یہ معلوم کرنے کے لئے کہا ہے کہ اگر کوئی اعادہ عنصر موجود ہے تو چھاپیں ، لیکن شرط یہ ہے کہ صف میں نمبر سب سے پہلے دہرانا عنصر ہونا چاہئے۔ صف میں جو اعداد پہلے دہرا رہے ہیں اس کا مطلوبہ جواب ہوگا ، یعنی ہم اسے دائیں سے بائیں کیوں منتقل کررہے ہیں۔ ہم ایک سیٹ استعمال کریں گے۔ سیٹ میں عام عنصر کو سیٹ میں محفوظ نہ کرنے کی خصوصیت موجود ہے۔ لہذا جب ہمیں صف میں ایک دہرایا گیا تو ہم صرف اس کی اشاریہ حاصل کرتے ہیں اور اس کے بعد انڈیکس کا عنصر چھاپتے ہیں۔

ہم ایک سیٹ کا اعلان کریں گے ، صف کے دائیں سے جانا شروع کریں گے ، ہم جانچیں گے کہ اگر سیٹ میں پہلے سے موجودہ صف عنصر کی قدر موجود ہے یا نہیں اگر اس میں موجود ہے تو اس کا اشاریہ حاصل کریں اور جھنڈے کی قیمت کو اس انڈیکس میں اپ ڈیٹ کریں ، اس پرچم کی قیمت ہم اسے بطور انڈیکس استعمال کریں گے اور بعد میں ہم اس قدر کو چھپائیں گے۔

اس سے پہلے ، ہمیں ٹریک کرتے وقت سرنی کی ساری قدریں داخل کرنی چاہ. ، لہذا جب ہمیں ایک جیسی قیمت مل جائے گی ، تو ہم اس عنصر کی اشاریہ کو اسٹور کریں گے۔ اگرچہ ہم دائیں سے صف کو عبور کررہے ہیں ، اگر ہمیں دائیں طرف کوئی عنصر مل گیا جو بائیں طرف دہرا رہا ہے تو اس کا مطلب ہے کہ یہ پہلا تکرار کرنے والا عنصر ہے۔ ہم پرچم کی قیمت کو اپ ڈیٹ کر رہے ہیں کیونکہ بعد میں ، ہم جانچ پڑتال کریں گے کہ آیا پرچم کی قیمت ابھی بھی -1 ہے یا اس کی تازہ کاری ہوئی ہے۔ اگر یہ اب بھی -1 ہے تو ، اس کا مطلب ہے کہ ہمیں کوئی اعادہ عنصر نہیں پایا گیا ، اگر اسے اپ ڈیٹ کر دیا جائے تو ہم پرچم کی اشاریہ اشاعت کو کسی صف کی پرنٹ کریں گے۔

ضابطے

پہلا کردار دہرانے کے لئے C ++ کوڈ

#include<bits/stdc++.h>

using namespace std;

void getFirstRepeatedElement(int arr[], int n)
{
    int Flag = -1;

    unordered_set<int> SET;

    for (int i = n - 1; i >= 0; i--)
    {
        if (SET.find(arr[i]) != SET.end())
            Flag = i;

        else
            SET.insert(arr[i]);
    }
    if (Flag!= -1)
        cout << "The first repeating element is " << arr[Flag];
    else
        cout << "There are no repeating elements";
}
int main()
{
    int arr[] = {2,6,9,3,1,9,1};

    int n = sizeof(arr) / sizeof(arr[0]);
    getFirstRepeatedElement (arr, n);
}
The first repeating element is 9

پہلا کردار دہرانے کے لئے جاوا کوڈ

import java.util.HashSet;

class FirstRepeatingElement
{
    public static void getFirstRepeatedElement (int arr[])
    {
        int Flag = -1;

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

        for (int i=arr.length-1; i>=0; i--)
        {
            if (SET.contains(arr[i]))
                Flag = i;

            else
                SET.add(arr[i]);
        }
        if (Flag!= -1)
            System.out.println("First repeating element is " + arr[Flag]);
        else
            System.out.println("No repeated element");
    }
    public static void main (String[] args)
    {
        int arr[] = {2,6,9,3,1,9,1};
        getFirstRepeatedElement(arr);
    }
}
First repeating element is 9

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔ چونکہ ہم ہیش سیٹ استعمال کررہے ہیں ، لہذا ہم اندراج اور O (1) کارروائیوں میں تلاش کرسکتے ہیں۔

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

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔