Algorithm
Problem Name: 88. Merge Sorted Array
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
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] with the underlined elements coming from nums1.
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 + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-109 <= nums1[i], nums2[j] <= 109
Code Examples
#1 Code Example with C Programming
Code -
C Programming
void merge(int* nums1, int m, int* nums2, int n) {
int k = m + n - 1;
m --;
n --;
while (n >= 0) {
while (m >= 0 && nums1[m] > nums2[n]) {
nums1[k--] = nums1[m--];
}
nums1[k--] = nums2[n--];
}
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for(int i = m - 1, j = n - 1; j >= 0;) nums1[i + j + 1] = (i < 0 || nums1[i] < nums2[j]) ? nums2[j--] : nums1[i--];
}
};
// longer.
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1;
while(i + j + 1 >= 0){
nums1[i + j + 1] = i < 0 ? nums2[j--] : j < 0 ? nums1[i--] : nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
}
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int endIdxOne = m - 1;
int endIdxTwo = n - 1;
int currIdx = m + n - 1;
while (endIdxOne >= 0 || endIdxTwo >= 0) {
if (endIdxOne >= 0 && endIdxTwo >= 0) {
if (nums1[endIdxOne] > nums2[endIdxTwo]) {
nums1[currIdx--] = nums1[endIdxOne--];
} else {
nums1[currIdx--] = nums2[endIdxTwo--];
}
} else if (endIdxOne >= 0 && endIdxTwo < 0) {
nums1[currIdx--] = nums1[endIdxOne--];
} else {
nums1[currIdx--] = nums2[endIdxTwo--];
}
}
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const merge = function(nums1, m, nums2, n) {
if (nums2.length === 0) return nums1;
let fi = 0;
let si = 0;
for (let i = si; i < n; i++) {
let se = nums2[i];
while (se >= nums1[fi] && fi < m + n && fi < m + i) {
fi++;
}
nums1.splice(fi, 0, se);
fi++;
}
while (nums1.length > m + n) {
nums1.pop();
}
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
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.
"""
while m > 0 and n > 0:
if nums1[m-1] >= nums2[n-1]:
nums1[m+n-1] = nums1[m-1]
m -= 1
else:
nums1[m+n-1] = nums2[n-1]
n -= 1
if n > 0:
nums1[:n] = nums2[:n]
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _088_MergeSortedArray
{
public void Merge(int[] nums1, int m, int[] nums2, int n)
{
m--;
n--;
for (var i = m + n + 1; i >= 0; i--)
{
if (m >= 0 && n >= 0)
if (nums1[m] >= nums2[n]) nums1[i] = nums1[m--];
else nums1[i] = nums2[n--];
else if (n >= 0)
nums1[i] = nums2[n--];
}
}
}
}
Input
Output