В этой статье блога мы рассмотрим различные методы объединения двух отсортированных массивов в C++. Объединение отсортированных массивов — распространенная задача в программировании, и понимание различных подходов может помочь вам писать эффективный и понятный код. Независимо от того, являетесь ли вы новичком или опытным разработчиком, это руководство предоставит вам ценную информацию и практические примеры кода.

Метод 1: наивный подход

Самый простой способ объединить два отсортированных массива — создать новый массив и перебрать два входных массива, сравнивая элементы и добавляя их в новый массив в правильном порядке. Вот пример реализации:

#include <iostream>
using namespace std;
void mergeArrays(int arr1[], int size1, int arr2[], int size2, int merged[]) {
    int i = 0, j = 0, k = 0;
    while (i < size1 && j < size2) {
        if (arr1[i] < arr2[j])
            merged[k++] = arr1[i++];
        else
            merged[k++] = arr2[j++];
    }
    while (i < size1)
        merged[k++] = arr1[i++];
    while (j < size2)
        merged[k++] = arr2[j++];
}
int main() {
    int arr1[] = {1, 3, 5, 7};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int arr2[] = {2, 4, 6, 8};
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    int merged[size1 + size2];
    mergeArrays(arr1, size1, arr2, size2, merged);
    cout << "Merged array: ";
    for (int i = 0; i < size1 + size2; i++)
        cout << merged[i] << " ";
    return 0;
}

Временная сложность этого подхода равна O(n), где n — общее количество элементов в обоих массивах.

Метод 2: использование дополнительного пространства

Если у вас есть дополнительная память, вы можете выделить новый массив размера (размер1 + размер2) и объединить массивы, используя ту же логику, что и в предыдущем методе. Этот подход позволяет упростить код и устраняет необходимость в граничных проверках. Вот пример:

#include <iostream>
using namespace std;
int* mergeArrays(int arr1[], int size1, int arr2[], int size2) {
    int* merged = new int[size1 + size2];
    int i = 0, j = 0, k = 0;
    while (i < size1 && j < size2) {
        if (arr1[i] < arr2[j])
            merged[k++] = arr1[i++];
        else
            merged[k++] = arr2[j++];
    }
    while (i < size1)
        merged[k++] = arr1[i++];
    while (j < size2)
        merged[k++] = arr2[j++];
    return merged;
}
int main() {
    int arr1[] = {1, 3, 5, 7};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int arr2[] = {2, 4, 6, 8};
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    int* merged = mergeArrays(arr1, size1, arr2, size2);
    cout << "Merged array: ";
    for (int i = 0; i < size1 + size2; i++)
        cout << merged[i] << " ";
    delete[] merged;
    return 0;
}

Метод 3: объединение на месте

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