# 88. Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
- 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 greater or equal to m + n) to hold additional elements from nums2.
Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
# Solution
Approach 1: Two pointers--From the beginning to the end of arrays.
Approach 2: Two pointers--From the end to the beginning of arrays.
# Code (Python)
Approach 2:
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
p1, p2, fill = m - 1, n - 1, m + n - 1
while p1 >= 0 and p2 >= 0:
if nums1[p1] >= nums2[p2]:
nums1[fill] = nums1[p1]
p1 -= 1
else:
nums1[fill] = nums2[p2]
p2 -= 1
fill -= 1
while p2 >= 0:
nums1[fill] = nums2[p2]
p2 -= 1
fill -= 1
# Code (C++)
Approach 1:
// From the beginning to the end.
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// First shift elements of nums1 to the end of the array.
for (int i = m + n - 1; i >= n; --i)
{
nums1[i] = nums1[i-n];
}
int p1 = n;
int p2 = 0;
for (int p3 = 0; p3 < m + n; ++p3)
{
if (p2 >= n || (p1 < m + n && nums1[p1] <= nums2[p2]))
{
nums1[p3] = nums1[p1];
p1++;
}
else
{
nums1[p3] = nums2[p2];
p2++;
}
}
}
};
Approach 2:
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1;
int p2 = n - 1;
int p3 = m + n - 1;
while (p1 >=0 || p2 >= 0)
{
if (p2 < 0 || (p1 >= 0 && nums1[p1] > nums2[p2]))
{
nums1[p3] = nums1[p1];
p1--;
}
else
{
nums1[p3] = nums2[p2];
p2--;
}
p3--;
}
}
};