Слияние последовательностей (#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();
    }
}