博文中会简要介绍Leetcode P0088题目分析及解题思路。
“Merge Sorted Array”是一道比较基础的数组题目，这道题和p0021有异曲同工之处，解决思路上基本一致。
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 equal to m + n) to hold additional elements from nums2.
有很多种实现思路，如果in-place的话时间复杂度最坏情况下是o(n^2)，或者是先把所有元素塞进数组然后统一排序，这样的话时间复杂度是O(nlogn)，也可以空间换时间，用一个额外数组存储元素，这样最多扫两遍即可，时间复杂度是O(n)。
以下是Java的题解代码实现。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] nums3 = new int[m+n];
int idx1 = 0, idx2 = 0, idx3 = 0;
while (idx1 < m || idx2 < n) {
int num1 = (idx1 < m)? nums1[idx1]: Integer.MAX_VALUE;
int num2 = (idx2 < n)? nums2[idx2]: Integer.MAX_VALUE;
if (num1 <= num2) {
nums3[idx3] = num1;
++idx1;
}
else {
nums3[idx3] = num2;
++idx2;
}
++idx3;
}
for (int idx=0; idx<m+n; ++idx)
nums1[idx] = nums3[idx];
}
}
以下是C++的题解代码实现。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> nums3;
int idx1 = 0, idx2 = 0;
while (idx1 < m || idx2 < n) {
int num1 = (idx1 < m)? nums1[idx1]: INT_MAX;
int num2 = (idx2 < n)? nums2[idx2]: INT_MAX;
if (num1 <= num2) {
nums3.push_back(num1);
++idx1;
}
else {
nums3.push_back(num2);
++idx2;
}
}
nums1 = nums3;
}
};