Merge Sorted Array
Given two sorted integer arrays nums1
and nums2
, merge nums2
into nums1
as one sorted array.
The number of elements initialized in nums1
and nums2
are m
and n
respectively. You may assume that nums1
has enough space (size that is equal to m + n
) to hold additional elements from nums2
.
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]
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Constraints:
0 <= n, m <= 200
1 <= n + m <= 200
nums1.length == m + n
nums2.length == n
-109 <= nums1[i], nums2[i] <= 109
Solutions
🧠 Cpp
class Solution
{
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
if(!n)
return;
if(!m)
{
nums1 = nums2;
return;
}
//merge two sorted arrays in one
auto n1_iter = nums1.begin(),
n1_end = n1_iter + m,
n2_iter = nums2.begin(),
n2_end = n2_iter + n;
vector<int> res;
res.reserve(n+m);
while(n1_iter != n1_end && n2_iter != n2_end)
if(*n1_iter < *n2_iter)
{
res.push_back(*n1_iter);
n1_iter++;
if(n1_iter == n1_end)
res.insert(end(res), n2_iter, n2_end);
}
else
{
res.push_back(*n2_iter);
n2_iter++;
if(n2_iter == n2_end)
res.insert(end(res), n1_iter, n1_end);
}
nums1 = std::move(res);
}
};
Last updated
Was this helpful?