Массивро ҷобаҷо кунед


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon Амдокс себ Блумберг Брука Facebook Голдман Sachs IBM Шабакаҳои арчаҳо LinkedIn Microsoft Quikr Snapdeal Synopsys Visa Зохо
тартиботи ҳарбӣ Sorting Ду нишоннамо

Дар якҷоягӣ мушкилоти массиви мураттабшуда, ки мо додаем ду навъ массиви дар афзоиши тартибот. Дар вуруд аввал, мо адади ба массиви1 ва массиви2 саршударо додем. Ин ду рақам N ва M мебошанд. Андозаи массиви 1 ба суммаи N ва M баробар аст. Дар массиви 1 n-и аввал сар мешавад ва m-и оянда 0-ро дар бар мегиранд. массиви2 боқӣ мемонад. Биёед формати зеринро барои фаҳмиши беҳтар дида бароем.

Формати вуруд

Сатри аввал, ки дорои ду ададҳои бутун N ва M мебошад.

Хатти дуввум, ки массиви 1-ро дар бар мегирад, ки дар он N рақами аввал сар мешавад ва рақами M навбатӣ 0 мебошанд.

Сатри сеюм дорои массиви2, ки рақамҳои М дорад.

Формат Натиҷа

Масви аввалро дар як сатр чоп кунед, ки дар он арзишҳо бо фосила ҷудо карда шаванд.

Маҳдудиятҳо

  • 0 <= N, M <= 100000
  • массиви 1 [i] <= | 1000000000 | ки дар он 0 <= i
  • массиви 2 [i] <= | 1000000000 |
Sample Input:
5 3
2 3 4 4 8 0 0 0
3 5 7
Sample Output:
2 3 3 4 4 5 7 8

Шарҳи Барои якҷоя кардани ду массиви ҷудошуда

Дар ин ҷо мо маҷбурем, ки ягон фазои иловагӣ эҷод карда натавонем, агар як майдони дигарро эҷод кунем асал барои нигоҳ доштани арзиш бо тартиби мураттаб, пас мо бояд мураккабии фазоии хатиро истифода барем. Ҳамин тавр, як равиши оддӣ барои илова кардани дуввум дар охири массиви1 ва сипас ҷобаҷогузории массив1. Дар ин ҳол, мо ягон фазои иловагӣ эҷод карда наметавонем ва танҳо дар вақти O (N * logN) ҳалли худро ёбем.

Алгоритми якҷоякунии массив

Step:1 Set j=0
Step:2 For i in range N to N+M-1:
           a) array1[i]=array2[j]
           b) j=j+1
Step:3 Sort the array1
Step:4 Print the array1

Татбиқи Барои Array Array Array

/*C++ Implementation of "Merge Sorted Array".*/ 
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{
    /*input values.*/
    int n,m;
    cin>>n>>m;
    int array1[n+m];
    for(int i=0;i<n+m;i++)
    {
        cin>>array1[i];
    }
    int array2[m];
    for(int i=0;i<m;i++)
    {
        cin>>array2[i];
    }
    /*add array2 at the end of array1.*/
    int j=0;
    for(int i=n;i<n+m;i++)
    {
        array1[i]=array2[j];
        j++;
    }
    sort(array1,array1+n+m);
    /*print array1*/
    for(int i=0;i<n+m;i++)
    {
        cout<<array1[i]<<" ";
    }
    return 0;
}
7 5
1 2 2 5 8 9 17 0 0 0 0 0
2 5 13 19 21
1 2 2 2 5 5 8 9 13 17 19 21

Мураккабии вақт

O (N * log N) зеро дар ин ҷо мо ҳунарнамоӣ мекунем навъ ки барои ба тартиб даровардани рақамҳои N вақти N * log N мегирад. Дар ин ҷо N андозаи массив аст1. Ин танҳо аз массиви аввал вобаста аст, зеро мо массиви дуюмро ба массиви якум илова мекунем. Андозаи массиви 1 ҳамеша аз массиви 2 зиёдтар аст.

Мураккабии фазо

О (1) зеро мо ба ҷои массиви вуруди худ ягон фазои изофӣ истифода намекунем. Мо танҳо ҳамаи арзишҳоро ба массиви1 гузоштем, ки андозаи онҳо аллакай ба мо дода шудааст. Ҳамин тавр, мо танҳо ҷобаҷогузорӣ мекунем ва натиҷаи худро бе фароҳам овардани фазои иловагӣ барои якҷоя кардани ду массив ба даст меорем.

Адабиёт