ایک صف لیٹ کوڈ حل میں غائب تمام نمبر تلاش کریں


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

مسئلہ یہ بیان

اس پریشانی میں ، ہمیں ایک دیا جاتا ہے صف عدد کا اس میں 1 سے N تک کے عناصر شامل ہیں ، جہاں صف کی N = سائز ہے۔ تاہم ، کچھ عناصر موجود ہیں جو غائب ہوگئے ہیں اور کچھ نقلیں ان کی جگہ پر موجود ہیں۔ ہمارا ہدف یہ ہے کہ ایسے تمام غائب اعشاریوں کی صف کو لوٹائیں۔

مثال کے طور پر

Array = {1 , 2 , 5 , 6 , 2 , 5}
3 4

ایک صف لیٹ کوڈ حل میں غائب تمام نمبر تلاش کریں

Array = {1 , 2 , 3 , 4}
n

ایک صف لیٹ کوڈ حل میں غائب تمام نمبر تلاش کریں

نقطہ نظر (ہیش سیٹ کا استعمال کرتے ہوئے)

ہم صف میں موجود ہر عنصر کو نشان زد کرسکتے ہیں اور پھر حد میں لوپ کرسکتے ہیں: [1 ، N] یہ جاننے کے لئے کہ کون سے کون سے عناصر غائب ہوگئے ہیں یا صف میں گم ہیں۔ ہم ذخیرہ کرنے کے لئے ہیش سیٹ کا استعمال کرتے ہیں چاہے کسی عدد کو نشان زد کیا گیا ہو یا نہیں۔

الگورتھم

  1. ہیش سیٹ شروع کریں نشان لگائیں [عدد] موجود عناصر کو ذخیرہ کرنے کے لئے۔
  2. ہر عنصر کے لئے i صف میں:
    • شامل کریں i کرنے کے لئے نشان
  3. ایک فہرست / ویکٹر شروع کریں نتیجہ صف میں لاپتہ عناصر کو ذخیرہ کرنے کے لئے
  4. ہر عنصر کے لئے حد میں: [1 ، N]:
    • If میں موجود نہیں ہے نشان:
      • اس میں شامل کریں نتیجہ
  5. واپس نتیجہ
  6. نتیجہ پرنٹ کریں

ایک صف لیٹ کوڈ حل میں غائب تمام نمبر تلاش کریں پر عمل درآمد

سی ++ پروگرام

#include <bits/stdc++.h>
using namespace std;

vector <int> findDisappearedNumbers(vector <int> &a)
{
    unordered_set <int> mark;
    for(int &i : a)
        mark.insert(i);
    int N = a.size();
    vector <int> result;
    for(int i = 1 ; i <= N ; i++)
        if(mark.find(i) == mark.end())
            result.emplace_back(i);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 5 , 6 , 2 , 5};
    vector <int> result = findDisappearedNumbers(a);
    if(result.empty())
        cout << "No disappeared elements\n";
    else
        for(int &i : result)
            cout << i << " ";
    return 0;
}

جاوا پروگرام

import java.util.*;

class find_disappeared_numbers
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 5 , 6 , 2 , 5};
        List <Integer> result = findDisappearedNumbers(a);
        if(result.size() == 0)
            System.out.println("No disappeared elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> findDisappearedNumbers(int[] a)
    {
        List <Integer> result = new ArrayList <Integer>();
        HashSet <Integer> mark = new HashSet <Integer>();
        for(int i : a)
            mark.add(i);

        for(int i = 1 ; i <= a.length ; i++)
            if(!mark.contains(i))
                result.add(i);

        return result;
    }
}
3 4

ایک صف لیٹ کوڈ حل میں غائب تمام نمبر تلاش کرنے کا پیچیدہ تجزیہ

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

O (N) جیسا کہ ہم ایک بار پوری صف کو عبور کرتے ہیں۔ N = سرنی کا سائز۔

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

O (N) جیسا کہ ہم وہ تمام نمبر جمع کرتے ہیں جو ایک ہیش ٹیبل میں صف میں موجود ہیں۔ نوٹ کریں کہ ہم خلائی پیچیدگی کے تعاون میں آؤٹ پٹ صف پر غور نہیں کرتے ہیں۔

نقطہ نظر (جگہ جگہ ترمیم)

اس مسئلے میں ایک نکتہ یہ ہے کہ: "صف میں ہمیشہ عناصر اس کے سائز سے کم یا برابر ہوتے ہیں"۔ اس کا مطلب یہ ہے کہ بہت سے اشارے جتنے الگ الگ عناصر ہیں۔ نیز ، غائب عناصر ہمیشہ ن (سرنی کا سائز) سے کم رہیں گے۔ اس رکاوٹ کا استعمال کرتے ہوئے ، ہم کسی بھی طرح سے کسی عدد کی موجودگی کو ذخیرہ کرنے کیلئے خود صف کا استعمال کرسکتے ہیں۔ مثال کے طور پر ، فرض کریں کہ ہم لکھ سکتے ہیں درست غلط کسی عنصر کے انڈیکس میں بالترتیب اس کی موجودگی / غیر موجودگی کی نشاندہی کرنا۔ ہمارے معاملے میں ، صف میں پہلے ہی عناصر شامل ہیں ، لہذا اس طرح کا ذخیرہ / یادداشت ناممکن نہیں ہے۔ تاہم ، چونکہ ہم جانتے ہیں کہ تمام عناصر مثبت ہیں ، لہذا ہم اشارہ کرنے کے اشارے کے طور پر "منفی" استعمال کرسکتے ہیں کہ آیا ہم نے صف میں کوئی عنصر دیکھا ہے یا نہیں۔ نوٹ کریں کہ ہم کچھ انڈیکس میں ذخیرہ شدہ اصل قدر استعمال کرکے حاصل کرسکتے ہیں مطلق () فنکشن جو ایک عدد کی مطلق قدر لوٹاتا ہے۔ اس طرح ، سرنی کو ہیش کا نقشہ اور کنٹینر دونوں کے طور پر استعمال کیا جاسکتا ہے۔

مثال کے طور پر ، اگر ہم نے صف میں عنصر '2' دیکھا ہے ، تو ہم ارے کو تفویض کرسکتے ہیں [1] = -1 * ارے [1] جو ہمیں بتائے گا کہ عنصر 2 سرنی میں نظر آرہا ہے۔

اگر ہم نے انڈیکس میں کوئی عنصر دیکھا ہوا ہے تو یہ چال اسٹور کو جگہ جگہ لے کر چلتی ہے i. ایک بار کام کرنے کے بعد ، ہم تمام انٹیجرز کو تلاش کرنے کے لئے رینج [1 ، N] میں ایک لوپ چلا سکتے ہیں جو غیر منفی ہیں (جس کا مطلب ہے کہ وہ نہیں دیکھا گیا ہے) اور اس وجہ سے ، مطلوبہ نتیجہ پرنٹ کریں۔ نوٹ کریں کہ یہ تب ہی ممکن ہے اگر ہم ہیں کی اجازت سرنی کو تبدیل کرنے کے لئے.

الگورتھم

  1. ہر عنصر کے لئے صف میں:
    • اگر صف [i - 1]> 0:
      • اسے منفی کے طور پر سیٹ کریں ، یا ، صف [i - 1] * = -1؛
  2. ایک فہرست / ویکٹر شروع کریں نتیجہ تمام لاپتہ عناصر کو ذخیرہ کرنے کے لئے
  3. ہر عدد کے لئے حد میں [1، N] (N = سائز کا صف):
    • If صف [i]> 0
      • اس عنصر کو شامل کریں i کرنے کے لئے نتیجہ
  4. واپس نتیجہ
  5. نتیجہ پرنٹ کریں

ایک صف لیٹ کوڈ حل میں غائب تمام نمبر تلاش کریں پر عمل درآمد

سی ++ پروگرام

#include <bits/stdc++.h>
using namespace std;

vector <int> findDisappearedNumbers(vector <int> &a)
{
    int N = a.size();
    int idx;
    for(int i = 0 ; i < N ; i++)
    {
        idx = abs(a[i]) - 1;
        if(a[idx] > 0)
            a[idx] *= -1;
    }

    vector <int> result;
    for(int i = 0 ; i < N ; i++)
        if(a[i] > 0)
            result.emplace_back(i + 1);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 5 , 6 , 2 , 5};
    vector <int> result = findDisappearedNumbers(a);
    if(result.empty())
        cout << "No disappeared elements\n";
    else
        for(int &i : result)
            cout << i << " ";
    return 0;
}

جاوا پروگرام

import java.util.*;
import java.lang.Math;

class find_disappeared_numbers
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 5 , 6 , 2 , 5};
        List <Integer> result = findDisappearedNumbers(a);
        if(result.size() == 0)
            System.out.println("No disappeared elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> findDisappearedNumbers(int[] a)
    {
        int idx;
        for(int i = 0 ; i < a.length ; i++)
        {
            idx = Math.abs(a[i]) - 1;
            if(a[idx] > 0)
                a[idx] *= -1;
        }

        List <Integer> result = new ArrayList <Integer> ();

        for(int i = 0 ; i < a.length ; i++)
            if(a[i] > 0)
                result.add(i + 1);

        return result;
    }
}
3 4

ایک صف لیٹ کوڈ حل میں غائب تمام نمبر تلاش کرنے کا پیچیدہ تجزیہ

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

O (N) چونکہ ہم غائب عناصر کو ڈھونڈنے کے لئے ان پٹ سے قطع نظر صف کے دو پاس چلاتے ہیں۔ N = سرنی کا سائز۔

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

O (1) چونکہ ہم مستقل میموری کی جگہ استعمال کرتے ہیں۔