Sıralanan Array birləşdirin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Amdoklar alma Bloomberg Brocade Facebook Goldman Sachs IBM Ardıc şəbəkələri LinkedIn microsoft Quikr Snapdeal Sinopsis Viza Zoho
Geyim çeşidləyici İki işarəBaxılıb 22

Birləşdirmək üçün sıralanmış sıra problemini verdik ikisi çeşidləndi seriallar artan qaydada. Əvvəlcə girişdə serial1 və array2 üçün başlanğıc sayını verdik. Bu iki nömrə N və M-dir. 1 massivin ölçüsü N və M-nin cəminə bərabərdir. 1-ci massivdə ilk n rəqəmi başlanğıclanır və sonrakı m-də 0 mövcuddur. 2-ci massivə 1-ci massivi əlavə etməliyik. array1 artan sırada qalır. Daha yaxşı başa düşmək üçün aşağıdakı formata baxaq.

Giriş Formatı

İki tam dəyər N və M olan birinci sətir.

İlk N ədədinin başlanğıc edildiyi və sonrakı M ədədlərinin 1 olduğu sıra 0-i ehtiva edən ikinci sətir.

M ədədlərini ehtiva edən 2 sıra olan üçüncü sətir.

Çıxış formatı

Birinci cərgəni dəyərlərin boşluqla ayrıldığı bir sətirdə çap edin.

Məhdudiyyətlər

  • 0 <= N, M <= 100000
  • array1 [i] <= | 1000000000 | burada 0 <= i
  • array2 [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

İki sıralanmış massivin birləşməsi üçün izah

Burada əlavə bir yer yaratsaq, əlavə bir yer yarada bilməyəcəyimizə bağlıyıq array dəyəri sıralanmış qaydada saxlamaq üçün xətti məkan mürəkkəbliyindən istifadə etməliyik. Beləliklə, array1-in sonunda ikincisini əlavə etmək və sonra array1-i sıralamaq üçün bir sadə yanaşma. Bununla əlavə bir boşluq yarada bilmirik və həllini yalnız O (N * logN) vaxtında tapa bilərik.

Birləşdirmə Alqoritmi Sıralanan Array

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

Birləşdirmə Sıralanan Array üçün İcra

/*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

Zamanın mürəkkəbliyi

O (N * log N) çünki burada çıxış edirik sıralama bu N nömrələrini sıralamaq üçün N * log N vaxtını alır. Burada N sıra 1-in ölçüsüdür. Yalnız birinci sıraya bağlıdır, çünki birinci massivə ikinci sıra əlavə edirik. 1-ci massivin ölçüsü həmişə 2-ci massivdən böyükdür.

Kosmik Mürəkkəblik

O (1) çünki giriş massivimizdən çox əlavə yer istifadə etmirik. Bütün dəyərləri yalnız ölçüsü artıq bizə verilən array1-ə qoyduq. Beləliklə, yalnız iki sıranı birləşdirmək üçün əlavə bir yer yaratmadan sıralama həyata keçiririk və nəticəmizi əldə edirik.

References

Translate »