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

Question

Задание: Даны два отсортированных в порядке неубывания массива. Необходимо слить их в один отсортированный массив. Нельзя просто добавить все элементы двух массивов в третий и отсортировать его. Необходимо сортировать элементы уже при добавлении в третий массив.

Моя реализация: `

#include <iostream>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    int *r_1 = new int[n];
    int *r_2 = new int[m];
    int *arr = new int[n + m];
    for (int i = 0; i < n; i ++){ cin >> r_1[i];
    }
    for (int i = 0; i < m; i ++){ cin >> r_2[i];
    }
    int count_n = 1, count_m = 1;
    if (r_1[0] > r_2[0]){
        arr[0] = r_2[0];
        count_n = 0;
    }
    else{
        arr[0] = r_1[0];
        count_m = 0;
    }

    for (int i = 1; i < (n + m); i ++){
        if (r_1[count_n] > r_2[count_m]){
            arr[i] = r_2[count_m];
            count_n --;
        }
        else{
            arr[i] = r_1[count_n];
            count_m --;
        }
        count_n ++;
        count_m ++;
    }
    for (int i = 0; i < (n + m); i ++){ cout << arr[i] << " ";
    }
}`

Проблема: Стабильно затирается последний элемент массива. Например для входных данных вида:

5 3
1 2 3 4 5
12 17 18

Программа выводит 1 2 3 4 5 0 12 17.

Answer 1

Навскидку (в принципе, основой цикл можно попытаться оптимизировать):

int main()
{
    int n, m;
    cin >> n >> m;
    int *r_1 = new int[n];
    int *r_2 = new int[m];
    int *arr = new int[n + m];
    for (int i = 0; i < n; i++) cin >> r_1[i];
    for (int i = 0; i < m; i++) cin >> r_2[i];

    for(int k = 0, i1 = 0, i2 = 0; k < n+m;)
    {
        if (i1 == n) arr[k++] = r_2[i2++];
        else if (i2 == m) arr[k++] = r_1[i1++];
        else if (r_1[i1] < r_2[i2]) arr[k++] = r_1[i1++];
        else arr[k++] = r_2[i2++];
    }

    for (int i = 0; i < (n + m); i++) cout << arr[i] << " ";
}

Answer 2

#include <vector>
#include <iostream>

int main() {
    std::vector<int> a {1, 2, 7, 10, 31}, b {0, 5, 7, 12, 30, 100};
    std::vector<int> ab(a.size() + b.size());

    auto ait = a.cbegin(), bit = b.cbegin();
    for (auto& v : ab) {
        v = ait != a.cend() ? (bit != b.cend() ? (*ait < *bit ? *ait++ : *bit++) : *ait++) : *bit++;
        std::cout << v << " ";
    }
    std::cout << std::endl; // 0 1 2 5 7 7 10 12 30 31 100
}

БЛОГ НА HUSL

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

Ответы (2 шт):