Ardıcıllıqları birləşdir (#9593)

Alqoritm Analizi

Hər iki ardıcıllığı bir massivə oxuyub onu sıralaya bilərik. Tapşırıq $O (n lo g_{2} n)$ vaxtında həll olunacaq.

Birləşdirmə, iki və ya daha çox sıralı ardıcıllığın bir sıralı ardıcıllığa birləşdirilməsi adlanır. Birləşdirmə STL-dən merge funksiyası istifadə edilərək edilə bilər. Mürəkkəblik $O (n)$ .

a və b ardıcıllıqlarının birləşdirilmə prosesini daha ətraflı nəzərdən keçirək. Üç dəyişən - göstəricilər p, q, i elan edək və onları belə təyin edək:

p = 0, birinci massiv anın əvvəlində;
q = 0, birinci massiv bnın əvvəlində;
i = 0, nəticədə əldə olunan massiv resin əvvəlində.

Hər addımda (iterasiyada) a[p] və b[q] dəyərlərini müqayisə edirik. Bu dəyərlərdən kiçik olanını res[i]ə mənimsədirik, sonra i göstəricisini və kiçik elementin göstəricisini (p və ya q) 1 vahid artırırıq. Məsələn, bir neçə addımdan sonra massivlərin belə bir vəziyyətə gələ bilər:

Massivlərdən birində göstərici sona çatdıqda, digər massivin qalan hissəsi nəticədə əldə olunan massivə kopyalanmalıdır.

Alqoritm İmplementasiyası

İşləyən massivləri elan edin.

vector<int> a, b, res;

İki giriş ardıcıllığını oxuyun.

scanf("%d", &n);
a.resize(n);
for (i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
b.resize(m);
for (i = 0; i < m; i++) scanf("%d", &b[i]);

Nəticədə əldə olunan ardıcıllığın ölçüsünü təyin edin - bu $n + m$ -yə bərabərdir.

res.resize(n + m);

Göstəriciləri başlanğıc vəziyyətə gətirin.

p = q = 0;

Hər iki göstərici massivin sonuna çatmayana qədər, res[i] = min(a[p], b[q]) təyin edin və uyğun göstəriciləri bir vahid irəli aparın.

for (i = 0; p < n && q < m; i++)
{
    if (a[p] <= b[q]) res[i] = a[p], p++;
    else res[i] = b[q], q++;
}

Göstəricilərdən biri massivin sonuna çatıb. İkinci massivin qalan hissəsini nəticədə əldə olunan massivə kopyalayın. Bu anda p = ndirsə, yalnız ikinci while işləyəcək. Bu anda q = mdirsə, yalnız birinci while işləyəcək.

while (p < n) res[i++] = a[p++];
while (q < m) res[i++] = b[q++];

Nəticədə əldə olunan ardıcıllığı çap edin.

for (i = 0; i < n + m; i++) printf("%d ", res[i]);
printf("\n");

Alqoritm İmplementasiyası - Sıralama

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int i, n, m;
vector<int> a;

int main(void)
{
    scanf("%d", &n);
    a.resize(n);
    for (i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    a.resize(n + m);
    for (i = 0; i < m; i++) scanf("%d", &a[n + i]);
    sort(a.begin(), a.end());
    for (i = 0; i < n + m; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Alqoritm İmplementasiyası - STL merge

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int i, n, m;
vector<int> a, b, res;

int main(void)
{
    scanf("%d", &n);
    a.resize(n);
    for (i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    b.resize(m);
    for (i = 0; i < m; i++) scanf("%d", &b[i]);
    res.resize(n + m);
    merge(a.begin(), a.end(), b.begin(), b.end(), res.begin());
    for (i = 0; i < n + m; i++) printf("%d ", res[i]);
    printf("\n");
    return 0;
}

Java İmplementasiyası

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner con = new Scanner(System.in);
        int n = con.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < n; i++)
            a[i] = con.nextInt();
        
        int m = con.nextInt();
        int b[] = new int[m];
        for(int i = 0; i < m; i++)
            b[i] = con.nextInt();
        
        int res[] = new int[n + m];
        int p = 0, q = 0, i;
        for (i = 0; p < n && q < m; i++)
        {
            if (a[p] <= b[q])
            {
                res[i] = a[p];
                p++;
            }
            else
            {
                res[i] = b[q];
                q++;
            }
        }
        
        while (p < n) res[i++] = a[p++];
        while (q < m) res[i++] = b[q++];
        
        for (i = 0; i < n + m; i++)
            System.out.print(res[i] + " ");
        System.out.println();
        con.close();
    }
}