ترتیب شدہ ارے لیٹکوڈ حل کو ضم کریں  


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایڈوب ایمیزون ایپل بلومبرگ ByteDance سسکو ای بے Expedia فیس بک گولڈمین سیکس گوگل IBM لنکڈ لفٹ مائیکروسافٹ Netflix کے اوریکل جھانکی Uber VMware یاہو Yandex
یلگوردمز لڑی کوڈنگ انٹرویو انٹرویو کی تیاری لیٹ کوڈ LeetCodeSolutions۔ دو پوائنٹر

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

مثال کے طور پر  

{1 , 2 , 3 , - , - , -}
{2 , 6 , 7}
1 2 2 3 6 7
{1 , 1 , 1 ,  - , -}
{2 , 4}
1 1 1 2 4

نقطہ نظر (چھانٹ رہا ہے)  

ہم دوسرے صف کے تمام عناصر کو پہلے والے میں منتقل کر سکتے ہیں۔ اس کے بعد ہم مطلوبہ نتیجہ حاصل کرنے کے لئے پہلی صف کو ترتیب دے سکتے ہیں۔

الگورتھم

  1. i = 0 سے i = N کیلئے ، تفویض کریں
    1. a [i + m] = b [i] ، a = پہلی صف ، b = دوسری صف
  2. پہلی صف کو ترتیب دیں
  3. مطلوبہ نتیجہ پرنٹ کریں

ضم شدہ ترتیب والے اشارے لیٹکوڈ حل کا نفاذ

سی ++ پروگرام

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

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    for(int i = 0 ; i < n ; i++)
        a[i + m] = b[i];

    sort(a.begin() , a.end());
    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

جاوا پروگرام

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        for(int i = 0 ; i < n ; i++)
            a[i + m] = b[i];
        Arrays.sort(a);
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}
1 2 2 3 6 7

مرجع شدہ ترتیب والے اشارے لیٹ کوڈ حل کا پیچیدہ تجزیہ

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

O (KlogK)، کہاں K = N + M۔. پہلی صف کا N = سائز ، دوسرا صف کا M = سائز۔ جیسا کہ ہم نے تمام N + M عناصر کو محفوظ کرنے کے بعد پہلی صف کو ترتیب دیا ہے۔

یہ بھی دیکھتے ہیں
اسٹرنگ لیٹ کوڈ حل میں کمی بڑھتی جارہی ہے

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

O (1) متغیر کے لئے مستقل میموری استعمال کی جاتی ہے۔

نقطہ نظر (دو نکات)  

ہم استعمال کر سکتے ہیں دو پوائنٹر دونوں ترتیب شدہ صفوں کو ایک نئی صف میں ضم کرنے کی تکنیک۔ لیکن ، اس نئی صف کی تشکیل میں اضافی جگہ خرچ ہوگی۔ ہم اس اضافی صف سے بچنے کی کوشش کر سکتے ہیں خصوصا when جب پہلی صف میں دونوں صفوں کے تمام عناصر کو رکھنے کے لئے کافی جگہ ہو۔ ہم دو پوائنٹرز استعمال کرسکتے ہیں اور پہلی صف کے پیچھے والے عناصر کو ملانا شروع کرسکتے ہیں۔

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

ترتیب شدہ ارے لیٹکوڈ حل کو ضم کریں

الگورتھم

  1. دو متغیرات کو شروع کریں i اور j پہلی اور دوسری صف کے آخری عنصر کے اشاریہ کو بالترتیب ذخیرہ کرنا۔
    • i = M - 1 ، j = N - 1
  2. ایک متغیر کو شروع کریں آئی ڈی ایکس، پہلی صف کا آخری انڈیکس اسٹور کر رہا ہے ، یعنی:
    • idx = N + M - 1
  3. اب ، مندرجہ ذیل میں سے کسی ایک تک کریں i or j صفر ہوجاتا ہے
    • اگر ایک [i]> = b [j]
      • ایک [idx] = a [i] ، کمی تفویض کریں i
    • ورنہ
      • ایک [idx] = b [j] ، کمی تفویض کریں j
    • کمی آئی ڈی ایکس
  4. دونوں میں سے i یا j صفر نہیں ہے ، جس کا مطلب ہے کچھ عناصر کو ابھی تک ضم کرنا باقی ہے۔ چونکہ وہ پہلے سے ہی ترتیب سے ہوتے ، ہم انہیں محض سامنے والے صف میں شامل کردیتے ہیں۔
  5. جبکہ i صفر نہیں ہوتا ،
    1. ایک [idx] = a [i] تفویض کریں
    2. کمی آئی ڈی ایکس اور i
  6. جبکہ j صفر نہیں ہوتا ،
    1. ایک [idx] = b [j] تفویض کریں
    2. کمی آئی ڈی ایکس اور j
  7. اب پہلے صف میں مطلوبہ ترتیب کے مطابق تمام عناصر موجود ہیں۔

ضم شدہ ترتیب والے اشارے لیٹکوڈ حل کا نفاذ

سی ++ پروگرام

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

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    int i = m - 1 , j = n - 1 , idx = m + n - 1;
    while(i >= 0 && j >= 0)
    {
        if(a[i] >= b[j])
        {
            a[idx] = a[i];
            i--;
        }
        else
        {
            a[idx] = b[j];
            j--;
        }
        idx--;
    }


    while(i >= 0)
        a[idx--] = a[i--];

    while(j >= 0)
        a[idx--] = b[j--];

    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

جاوا پروگرام

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        int i = m - 1 , j = n - 1 , idx = m + n - 1;
        while(i >= 0 && j >= 0)
        {
            if(a[i] >= b[j])
            {
                a[idx] = a[i];
                i--;
            }
            else
            {
                a[idx] = b[j];
                j--;
            }
            idx--;
        }

        while(i >= 0)
            a[idx--] = a[i--];

        while(j >= 0)
            a[idx--] = b[j--];

        return;
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}
1 2 2 3 6 7

مرجع شدہ ترتیب والے اشارے لیٹ کوڈ حل کا پیچیدہ تجزیہ

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

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

یہ بھی دیکھتے ہیں
چار لیٹکوڈ حل کی طاقت

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

O (1) ، جیسا کہ ہم سب عناصر کو پہلی صف میں محفوظ کرتے ہیں۔ تو ، الگورتھم ہے جگہ.