Merge Sorted Array
Question
- leetcode: Merge Sorted Array | LeetCode OJ
- lintcode: (6) Merge Sorted Array
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Example
A = [1, 2, 3, empty, empty], B = [4, 5]
After merge, A will be filled as [1, 2, 3, 4, 5]
Note
You may assume that A has enough space (size that is greater or equal to m + n)
to hold additional elements from B.
The number of elements initialized in A and B are m and n respectively.
题解
因为本题有 in-place 的限制，故必须从数组末尾的两个元素开始比较；否则就会产生挪动，一旦挪动就会是 $O(n^2)$ 的。
自尾部向首部逐个比较两个数组内的元素，取较大的置于数组 A 中。由于 A 的容量较 B 大，故最后 m == 0 或者 n == 0 时仅需处理 B 中的元素，因为 A 中的元素已经在 A 中，无需处理。
C++
class Solution {
public:
void merge(vector<int>& A, int m, vector<int>& B, int n) {
int index = m + n - 1;
while (m > 0 && n > 0) {
if (A[m - 1] > B[n - 1]) {
A[index] = A[m - 1];
--m;
} else {
A[index] = B[n - 1];
--n;
}
--index;
}
// 如果B非空，因为A中的元素已经在A中，m==0时，A中元素位置已调整好，B中元素不定
while (n > 0) {
A[index] = B[n - 1];
--n;
--index;
}
}
};
复杂度分析
最坏情况下需要遍历两个数组中所有元素，时间复杂度为 $O(m+n)$. 空间复杂度 $O(1)$.
