There are two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. nums1 has enough space to hold additional elements from nums2. The number of elements in nums1 and nums2 are m and n respectively.
Copy and Sort
Sorting all elements has time complexity is O(NLogN) where N is the number of the elements to sort. We need first to copy all the elements from second array to the first array before we apply sorting.
1 2 3 4 5 6 7 8 9 | class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { for (int i = m; i < m + n; i ++) { nums1[i] = nums2[i - m]; } sort(nums1.begin(), nums1.end()); } }; |
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for (int i = m; i < m + n; i ++) {
nums1[i] = nums2[i - m];
}
sort(nums1.begin(), nums1.end());
}
};The complexity is O(TLogT) where T = M + N.
Two Pointers Merging in O(Max(M, N))
Merging two sorted array is the foundation of the Merge-Sort, where you would have two index pointers pointing to two sorted sub arrays. Comparing each element at both array and deciding which one is minimal. The following has O(m+n) space and elements are pushed into the new temp array. At last, the array is assigned back to the first array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { vector<int> r(m + n); int i = 0, j = 0, k = 0; while (i < m && j < n) { if (nums1[i] <= nums2[j]) { r[k ++] = nums1[i ++]; } else { r[k ++] = nums2[j ++]; } } while (i < m) { r[k ++] = nums1[i ++]; } while (j < n) { r[k ++] = nums2[j ++]; } nums1 = r; } }; |
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> r(m + n);
int i = 0, j = 0, k = 0;
while (i < m && j < n) {
if (nums1[i] <= nums2[j]) {
r[k ++] = nums1[i ++];
} else {
r[k ++] = nums2[j ++];
}
}
while (i < m) {
r[k ++] = nums1[i ++];
}
while (j < n) {
r[k ++] = nums2[j ++];
}
nums1 = r;
}
};The complexity is O(Max(M, N)) where M and N are the length for two sorted list respectively. This approach, however requires additional O(M+N) space to keep the result and copy the result back to destination.
Two Pointers Merging Sorted Array
If you merge the numbers from the end, then you don’t need another array.
1 2 3 4 5 6 7 8 9 | void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { for (int num1r = m - 1, num2r = n - 1, wi = m + n - 1; num2r >= 0; --wi) { if (num1r >= 0 && nums1[num1r] > nums2[num2r]) { nums1[wi] = nums1[num1r--]; } else { nums1[wi] = nums2[num2r--]; } } } |
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for (int num1r = m - 1, num2r = n - 1, wi = m + n - 1; num2r >= 0; --wi) {
if (num1r >= 0 && nums1[num1r] > nums2[num2r]) {
nums1[wi] = nums1[num1r--];
} else {
nums1[wi] = nums2[num2r--];
}
}
}Another two pointer implementation that process both array from right to the left:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) int k = m + n - 1; int i = m - 1; int j = n - 1; while ((i >= 0) && (j >= 0)) { if (nums1[i] < nums2[j]) { nums1[k --] = nums2[j]; j --; } else { nums1[k --] = nums1[i]; i --; } } while (i >= 0) { nums1[k --] = nums1[i --]; } while (j >= 0) { nums1[k --] = nums2[j --]; } } }; |
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
int k = m + n - 1;
int i = m - 1;
int j = n - 1;
while ((i >= 0) && (j >= 0)) {
if (nums1[i] < nums2[j]) {
nums1[k --] = nums2[j];
j --;
} else {
nums1[k --] = nums1[i];
i --;
}
}
while (i >= 0) {
nums1[k --] = nums1[i --];
}
while (j >= 0) {
nums1[k --] = nums2[j --];
}
}
};The last two implementations has O(Max(M, N)) time and O(1) constant space.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Swap Nodes in Pairs in a Singly Linked List?
Next Post: How to Fix Corruption in Resource Version Files?
