# 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;
}
``````