Skip to content

11602: 【原1602】Merge Sorted Array

题目

题目描述

author: Online Judge 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1602

Description

Given two sorted positive integer arrays num1 with length m and num2 with length n, merge num2 into num1 as one sorted array.

Note:

  • You may assume that num1 has enough space (size that is greater or equal to (m+n) to hold additional elements from num2.
  • Initially, the number of elements in num1 and in num2 are m and n respectively.
  • Your input should be two sorted arrays. Moreover, the output should be the merged sorted array.
  • Every element from num1 and num2 should not exceed 10000.
  • You need to consider all the circumstances, for example, one array is empty set.

Sample Input

3
3
1 5 7
2 4 6

Sample Output

1 2 4 5 6 7

Neight99's solution

#include <iostream>

using namespace std;

void merge(int *&, int *&, int, int);

int main() {
    int N, M, *num1, *num2;

    cin >> N >> M;
    num1 = new int[N + 10];
    num2 = new int[M + 10];

    for (int i = 0; i < N; i++) {
        cin >> num1[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> num2[i];
    }

    if (N == 0) {
        for (int i = 0; i < M; i++) {
            cout << num2[i] << ' ';
        }
    } else if (M == 0) {
        for (int i = 0; i < N; i++) {
            cout << num1[i] << ' ';
        }
    } else if (N == 0 && M == 0) {
        cout << ' ';
    } else {
        merge(num1, num2, N, M);
        for (int i = 0; i < N + M; i++) {
            cout << num1[i] << ' ';
        }
    }

    delete[] num1;
    delete[] num2;
    return 0;
}

void merge(int *&num1, int *&num2, int N, int M) {
    int *ans = new int[N + M + 10], l = 0, r = 0, i = 0;

    while (l < N && r < M) {
        if (num1[l] < num2[r]) {
            ans[i++] = num1[l++];
        } else {
            ans[i++] = num2[r++];
        }
    }

    if (l == N) {
        while (r < M) {
            ans[i++] = num2[r++];
        }
    } else if (r == M) {
        while (l < N) {
            ans[i++] = num1[l++];
        }
    }

    delete[] num1;
    num1 = 0;
    num1 = ans;
}