Злиття послідовностей (#9593)

Аналіз алгоритму

Можна прочитати обидві послідовності в один масив і відсортувати його. Задача буде вирішена за час $O (n lo g_{2} n)$ .

Злиття будемо називати об'єднання двох (або більше) впорядкованих послідовностей в одну впорядковану послідовність. Злиття можна здійснити за допомогою функції merge з STL. Складність $O (n)$ .

Розглянемо процес злиття послідовностей a і b детальніше. Оголосимо три змінні – вказівники p, q, i і встановимо їх:

p = 0, на початок першого масиву a;
q = 0, на початок першого масиву b;
i = 0, на початок результуючого масиву res.

На кожному кроці (ітерації) порівнюємо значення a[p] і b[q]. Менше з цих значень присвоюємо res[i], після чого збільшуємо на 1 вказівник i і вказівник на менший елемент (p або q). Наприклад, після кількох кроків ми можемо отримати наступний стан масивів:

Коли вказівник у одному з масивів дійде до кінця, то залишкову частину іншого масиву слід скопіювати в результуючий масив.

Реалізація алгоритму

Оголосимо робочі масиви.

vector<int> a, b, res;

Читаємо дві вхідні послідовності.

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 + m$ .

res.resize(n + m);

Ініціалізуємо вказівники.

p = q = 0;

Поки жоден з вказівників не дійшов до кінця масиву, присвоюємо res[i] = min(a[p], b[q]) і просуваємо вперед на одиницю відповідні вказівники.

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

Один з вказівників дійшов до кінця масиву. Скопіюємо залишок другого масиву в результуючий. Якщо на даний момент p = n, то спрацює тільки другий while. Якщо на даний момент q = m, то спрацює тільки перший while.

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

Виводимо результуючу послідовність.

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

Реалізація алгоритму – сортування

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

Реалізація алгоритму – 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 реалізація

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();
    }
}