You are given two non-descending arrays of integers, nums1 and nums2, and two integers, m and n, representing the number of elements in nums1 and nums2, respectively.
Please merge nums2 into nums1 so that the merged array is also in non-descending order.
Note: Finally, the merged array should not be returned by the function, but stored in the array nums1. To deal with this, nums1 has an initial length of m + n, where the first m elements represent the elements that should be combined and the last n elements are 0 and should be ignored. Nums2 has a length of n.
Example 1:
Input:
,2,3,0,0,0 nums1 = [1], m = 3, nums2 = [6] 2, n = 3
Output:
,2,2,3,5,6 [1]
Explanation:
You need to merge [1,2,3] and [2,5,6].Copy the codeCombined results:
[1,2,2,3,5,6], where the elements in bold are nums1.
Example 2:
Input:
nums1 = [1], m = 1, nums2 = [], n = 0
Output:
[1]
Explanation:
[1] and [].
Combined results:
[1].
Example 3:
Input:
nums1 = [0], m = 0, nums2 = [1], n = 1
Output:
[1]
Explanation:
The arrays to merge are '[]' and '[1]'.Copy the codeCombined results:
[1].
Note:
Since m = 0, nums1 has no elements. The only zeros left in NUMs1 are simply to ensure that the merge results can be safely stored in NUMs1.Copy the code
Tip:
- nums1.length == m + n
- nums2.length == n
- 0 <= m, n <= 200
- 1 <= m + n <= 200
<= nums1[i], nums2[j] <=
Code:
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for(int i = m , j = 0; i < m + n ; i ++ )
nums1[i] = nums2[j++];
sort(nums1.begin(),nums1.end()); }};Copy the codeIdeas:
In this case, the two arrays have been identified, and we just need to make sure that the array is sorted in non-decreasing order. Therefore, we can merge all the elements of nums2 into nums1 and sort them later.Copy the codeComplexity analysis:
-
Time complexity: O((m+n)log(m+n)). The length of the sorting sequence is M + N, and the time complexity of quicksort is O((m+n)log(m+n)) on average.
-
Space complexity: O(log(m+n)). The length of the sorting sequence is M + N, and the space complexity of quicksort can be applied. The average case is O(log(m+n)).
Official Code 1:
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = 0, p2 = 0;
int sorted[m + n];
int cur;
while (p1 < m || p2 < n) {
if (p1 == m) {
cur = nums2[p2++];
} else if (p2 == n) {
cur = nums1[p1++];
} else if (nums1[p1] < nums2[p2]) {
cur = nums1[p1++];
} else {
cur = nums2[p2++];
}
sorted[p1 + p2 - 1] = cur;
}
for (int i = 0; i ! = m + n; ++i) { nums1[i] = sorted[i]; }}};Copy the codeIdeas:
Use the property that the array nums1 and array nums2 have been sorted. To take advantage of this property, we can use the two-pointer method. This method treats the two arrays as queues, and each time it takes a smaller number from the head of each array and puts it into the result.Copy the codeComplexity analysis:
-
Time complexity: O(m+ N). Pointer movement is monotonically increasing, at most m+ N times, so the time complexity is O(m+ N).
-
Space complexity: O(m+ N). We need to create a sorted intermediate array of length m+n.
Official Code 2:
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1;
int tail = m + n - 1;
int cur;
while (p1 >= 0 || p2 >= 0) {
if (p1 == - 1) {
cur = nums2[p2--];
} else if (p2 == - 1) {
cur = nums1[p1--];
} else if (nums1[p1] > nums2[p2]) {
cur = nums1[p1--];
} else{ cur = nums2[p2--]; } nums1[tail--] = cur; }}};Copy the codeIdeas:
It is observed that the latter part of NUMS1 is empty and can be directly overwritten without affecting the results. Therefore, the pointer can be set to traverse backwards and forwards, taking the larger of the two and putting it at the end of NUMs1. Strictly speaking, at any time during this traversal, m− P1 − 1M − P_1 − 1M − P1 −1 elements in nums1 are placed in the last half of NUMs1, and N − P2 − 1N − P_2 − 1N − P2 −1 elements in NUMS2 are placed in the last half of NUMs1. After the pointer p1P_1P1, nums1 has positions m+ N − P1 −1m+ N-p1 -1m+ N − P1 −1. Due to the m + n – p1-1 m or more – p1-1 + 1 m + n – n – p2 – p_1-1 m or more – p_1-1 + 1 m + n – n – p_2 – p1-1 m or more – p1-1 + n – p2 – equivalent to a p2 – or 1 p_2 acuity p2-1-1 or more established forever, Thus, the space behind p1p_1P1 is always large enough to hold the inserted element without causing the element of P1p_1P1 to be overwritten.
Complexity analysis:
- Time complexity: O(m+ N). Pointer movement is monotonically decreasing, at most m+ N times, so the time complexity is O(m+ N).
- Space complexity: O(1). The nums1 array is modified directly in place, requiring no extra space.