9593. Слияние
последовательностей
Заданы две отсортированные
последовательности. Произведите их слияние.
Вход.
Первая строка содержит длину первой последовательности n (n ≤ 106), за которой
следуют n целых чисел в
отсортированном порядке.
Вторая строка содержит длину
второй последовательности m (m ≤ 106), за которой следуют m целых чисел в
отсортированном порядке.
Выход.
Произведите слияние двух последовательностей и выведите результирующую в одной
строке.
|
Пример входа |
Пример выхода |
|
5 2 4 6 7 9 6 1 2 2 4 5 6 |
1 2 2 2 4 4 5 6 6 7 9 |
РЕШЕНИЕ
последовательности
Анализ алгоритма
Можно прочитать обе
последовательности в один массив и отсортировать его. Задача будет решена за
время O(nlog2n).
Слиянием будем называть
объединение двух (или более) упорядоченных последовательностей в одну упорядоченную последовательность. Слияние можно совершить при
помощи функции 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();
}
}