د ترتیب شوي اریز لیټکوډ حل حل کړئ  


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ایڈوب ترلاسه کړئ Amazon مڼه د بلومبرګ ByteDance سیسکو ebay لکه ايکسپيډيا فیسبوک ګولډمن Sachs د ګوګل IBM LinkedIn لفټ د Microsoft Netflix سينه_پوښ جدولاو über VMware د ياهو Yandex
الگوريتم پیشه کوډ ورکول مرکه د مرکې چمتووالی لیټ کوډ د لیټ کوډ حلونه دوه نښې

په ستونزه کې "ضمیمه شوي اریزونه" ، موږ ته دوه راکول شوي تیرونه په نه کښته ترتیب کې ترتیب شوی. لومړی صف په بشپړ ډول ندی ډک شوی او کافي ځای لري چې د دوهم سرلیکونکي ټول عناصر هم ځای په ځای کړي. موږ باید دوه سرګړي یوځای کړو ، داسې چې په لومړي سر کې د دواړه سرنو عناصرې شاملې وي او په ترتیب ډول ترتیب شوي نه ښکته کیدونکی امر

بېلګه  

{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. اړینه پا Printه چاپ کړئ

د یوځای شوي ترتیب شوي تیرونو لیټکوډ حل پلي کول

C ++ برنامه

#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) لکه څنګه چې مستقل حافظه د متغیرونو لپاره کارول کیږي.

چلند (دوه نښې)  

موږ کولی شو کار وکړو دوه نښې تخنیک چې دوه ترتیب شوي بraې په نوي صف کې ترکیب کړئ. مګر ، د دې نوي صف رامینځته کول به اضافي ځای مصرف کړي. موږ کولی شو هڅه وکړو چې د دې اضافي صفاتو مخه ونیسو په ځانګړي توګه کله چې لومړی سرنی کافي ځای ولري چې د دواړو تیرونو ټول عناصر وساتي. موږ کولی شو دوه نښې وکاروو او د لومړي صف په شا کې د عناصرو ضم کول پیل کړو.

دا به د "اضافي سرې حافظې" ستونزه راټیټه کړي ځکه چې موږ په باطل ځای کې د عناصرو اصلاح کولو ته دوام ورکوو.

د ترتیب شوي اریز لیټکوډ حل حل کړئ

الګوریتم

  1. دوه تغیرات پیل کړئ i او j په ترتیب سره د لومړي او دوهم صف د وروستي عنصر شاخصونه ساتي.
    • i = M - 1 ، j = N - 1
  2. یو متغیر پیل کړئ idx، د لومړي صف وروستی شاخص ساتل ، دا دي:
    • idx = N + M - 1
  3. اوس ، لاندې د یو نه پورې ترسره کړئ i or j صفر کیږي
    • که A [i]> = b [j]
      • یو [idx] = a [i] ، کمښت i
    • د
      • یو [idx] = b [j] ، کمښت j
    • کمښت idx
  4. د i یا j صفر ندی ، پدې معنی چې یو شمیر عناصر لا یوځای شوي دي. لکه څنګه چې دوی به دمخه په ترتیب شوي ډول وي ، موږ په ساده ډول دوی په مخکینۍ قطار کې ضمیمه کوو.
  5. په داسې حال کې i صفر نه کیږي ،
    1. د [idx] = a [i] ټاکل
    2. کمښت idx او i
  6. په داسې حال کې j صفر نه کیږي ،
    1. د [idx] = b [j] مقرر کړئ
    2. کمښت idx او j
  7. اوس لومړی صف د مطلوب ترتیب شوي ترتیب کې ټول عناصر لري.

د یوځای شوي ترتیب شوي تیرونو لیټکوډ حل پلي کول

C ++ برنامه

#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) ، لکه څنګه چې موږ ټول عناصر په لومړي صف کې ذخیره کوو. نو ، الګوریتم دی په ځای کی.