Sıralanan Diziler Leetcode Çözümünü Birləşdirin

"Sıralanmış massivləri birləşdir" problemində bizə ikisi verilir seriallar azalan qaydada sıralanır. Birinci sıra tam doldurulmamışdır və ikinci sıra bütün elementlərini yerləşdirmək üçün kifayət qədər yerə sahibdir. İki massivi birləşdirməliyik, belə ki, birinci sıra hər iki massivin elementlərini ehtiva edir və sıralanır enməyən üçün.

misal

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

1 2 2 3 6 7

{1 , 1 , 1 ,  - , -}
{2 , 4}

1 1 1 2 4

Yanaşma (çeşidləmə)

İkinci sıra bütün elementlərini birincisinə köçürə bilərik. Daha sonra lazımi nəticəni əldə etmək üçün ilk sıranı sıralaya bilərik.

Alqoritm

1. İ = 0 - i = N arasında təyin edin
   1. a [i + m] = b [i], a = birinci sıra, b = ikinci sıra
2. Birinci sıranı sıralayın
3. Lazımi nəticəni çap edin

Birləşdirmə Sıralanan Array Leetcode Solution tətbiq edilməsi

C ++ Proqramı

#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;
}

Java Proqramı

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

Birləşdirmə Sortlaşdırılan Array Leetcode Həllinin Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (KlogK), Harada K = N + M. N = birinci massivin ölçüsü, M = ikinci massivin ölçüsü. Birinci sıra bütün N + M elementlərini saxladıqdan sonra çeşidləyərkən.

Kosmik Mürəkkəblik

O (1) kimi dəyişkənlər üçün daimi yaddaş istifadə olunur.

Yanaşma (iki göstərici)

Biz istifadə edə bilərsiniz iki göstərici iki sıralanmış massivi yeni bir sıra halına gətirmək üçün texnika. Ancaq bu yeni massivin yaradılması əlavə yerə başa gələcək. Xüsusilə ilk sıra hər iki massivin bütün elementlərini tutacaq qədər yer tutduqda bu əlavə massivdən qaçmağa çalışa bilərik. İki göstəricidən istifadə edib birinci massivin arxasındakı elementləri birləşdirməyə başlaya bilərik.

Boşluqdakı elementləri düzəltməyə davam etdikdə, bu "əlavə sıra yaddaşı" problemini həll edəcəkdir.

Pin

Alqoritm

1. İki dəyişən başlayın i və j müvafiq olaraq birinci və ikinci massivin son elementinin göstəricilərinin saxlanması.
   • i = M - 1, j = N - 1
2. Dəyişəni başladın idx, ilk massivin son indeksinin saxlanması, yəni:
   • idx = N + M - 1
3. İndi, hər hansı birinə qədər aşağıdakıları edin i or j sıfır olur
   • A [i]> = b [j] olarsa
     • A [idx] = a [i], azalma təyin edin i
   • Daha
     • A [idx] = b [j] təyin edin, azalma j
   • Azalma idx
4. Həm də mən və ya j sıfır deyil, bəzi elementlərin hələ birləşdirilməli olduğu mənasını verir. Onsuz da sıralanmış bir şəkildə olacağı üçün onları sadəcə öndəki ilk sıraya əlavə edirik.
5. Isə i sıfır olmur,
   1. A [idx] = a [i] təyin edin
   2. Azalma idx və i
6. Isə j sıfır olmur,
   1. Bir [idx] = b [j] təyin edin
   2. Azalma idx və j
7. İndi ilk sıra bütün elementləri tələb olunan sıralanmış qaydada saxlayır.

Birləşdirmə Sıralanan Array Leetcode Solution tətbiq edilməsi

C ++ Proqramı

#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;
}

Java Proqramı

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

Birləşdirmə Sortlaşdırılan Array Leetcode Həllinin Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N + M). N = birinci sıra ölçüsü, M = ikinci sıra ölçüsü. Hər iki massivi bir dəfə keçdikdə.

Kosmik Mürəkkəblik

O (1), bütün elementləri birinci massivdə saxladığımız üçün. Beləliklə, alqoritm belədir yerində.