Merge Sorted Arrays Lab
In this lab, you will be working on merging two integer arrays, nums1
and nums2
, which are sorted in non-decreasing order. The goal is to merge them into a single combined array, sorted in a non-decreasing order, and store it inside the array nums1
. The input arrays are represented by nums1
, nums2
, and their respective element counts m
and n
.
The array nums1
has a length of m + n
, with the first m
elements being the initial elements that need to be merged and the last n
elements being set to 0
and ignored. The array nums2
has a length of n
.
Examples
Example 1
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6].
Example 2
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and []. The result of the merge is [1].
Example 3
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1]. The result of the merge is [1]. Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.
Constraints
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
Follow-up
Can you come up with an algorithm that runs in O(m + n) time?