Слияние массивов

Слияние массивов — это построение одной последовательности из двух исходных с сохранением относительного порядка элементов. Приём особенно полезен, когда массивы уже упорядочены: тогда их можно объединить за один проход методом двух указателей, не выполняя полную сортировку заново.

Что такое слияние массивов

Пусть даны последовательности \(A\) и \(B\). Нужно получить последовательность \(C\), содержащую все элементы \(A\) и \(B\). Если длины массивов равны \(n\) и \(m\), то длина результата равна \(n+m\). Слияние не удаляет повторяющиеся элементы и не меняет порядок элементов внутри каждого исходного массива.

Например, при слиянии \(A=(1,4,8)\) и \(B=(2,3,9)\) получаем \(C=(1,2,3,4,8,9)\). Но слияние возможно и для неотсортированных последовательностей: тогда сохраняется порядок элементов, однако результат не обязан быть отсортированным. Например, \(A=(5,1)\) и \(B=(4,2)\) можно объединить как \((5,1,4,2)\) или \((5,4,1,2)\) — выбор зависит от дополнительного условия задачи.

Слияние отсортированных массивов

Для отсортированных массивов применяется метод двух указателей. Указатель \(i\) показывает первый неиспользованный элемент массива \(A\), а \(j\) — первый неиспользованный элемент массива \(B\). В начале \(i=0\) и \(j=0\) при нумерации с нуля.

1. Пока в обоих массивах есть неиспользованные элементы, сравниваются \(A[i]\) и \(B[j]\).
2. В результат записывается меньший элемент; указатель соответствующего массива увеличивается на один.
3. Когда один массив заканчивается, все оставшиеся элементы второго добавляются в конец результата.

Если элементы равны, можно взять элемент из любого массива. В задачах, где нужно сохранить устойчивость — например, порядок одинаковых ключей, — обычно сначала выбирают элемент из \(A\). Для обычного объединения числовых массивов это различие не влияет на значения результата.

def merge(a, b):
    i = 0
    j = 0
    result = []

    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1

    result.extend(a[i:])
    result.extend(b[j:])
    return result

Почему алгоритм работает быстро

Каждый элемент каждого массива переносится в результат ровно один раз. Указатели только увеличиваются и никогда не возвращаются назад. Поэтому число действий пропорционально общей длине массивов.

Дополнительная память для нового массива равна \(O(n+m)\). Если требуется изменить один из массивов на месте, алгоритм может быть другим; в школьных задачах обычно создают отдельный массив результата.

Разобранный пример

Даны два отсортированных массива: \(A=(2,5,7,12)\) и \(B=(1,5,6,10,13)\). Требуется получить их объединение по возрастанию. Обозначим текущие позиции указателей через \(i\) и \(j\).

Слияние в задачах с условиями

В экзаменационных задачах требуется не только слить массивы полностью. Иногда нужно посчитать количество общих элементов, сформировать пересечение, удалить повторы или слить строки. Основная идея остаётся прежней: указатели движутся только вперёд.

• Для объединения с сохранением повторов записывайте меньший элемент и увеличивайте один указатель.
• Для пересечения записывайте элемент только при равенстве \(A[i]=B[j]\), затем увеличивайте оба указателя.
• Для подсчёта элементов, встречающихся в обоих массивах, при равенстве увеличивайте счётчик.
• Для удаления повторов проверяйте, отличается ли новый элемент от последнего уже записанного.

Если исходные массивы не отсортированы, сначала может потребоваться сортировка массива. В зависимости от условия используют сортировку по возрастанию или сортировку по убыванию. После сортировки можно применить слияние, но важно учитывать: сортировка меняет исходный порядок.

Для строк слияние выполняется аналогично: строку можно рассматривать как последовательность символов. Например, при слиянии строк в лексикографическом порядке сравниваются текущие символы, а затем дописывается остаток одной строки. Если задача связана с подсчётом повторов, полезны частота элемента и таблица частот.

Частые ошибки

Алгоритм проверки решения

• Проверить, что длина результата равна сумме длин исходных массивов.
• Проверить, что каждый исходный элемент встречается в результате нужное число раз.
• Проверить порядок: последовательность элементов каждого массива не изменился.
• Если массивы отсортированы, проверить сортировку результата.
• Отдельно протестировать пустой массив и случай равных элементов.