网站建设工资 优帮云/代写文章平台

1 题目

题目：将有序数组并入另一个有序数组（Merge Sorted Arrays）
描述：将按升序排序的整数数组A和B合并，新数组也需有序。

1. 假设被并入的数组会有足够空间容纳另一个数组。

lintcode题号——暂无，难度——easy

样例1：

输入：
A = [1,2,3,null,null]
B = [4,5]
输出：A = [1,2,3,4,5]
解释：返回合并后的数组。

样例2：

输入：
A = [1,2,null]
B = [1]
输出：A = [1,1,2]

2 解决方案

2.1 思路

  将两个已排序的数组合并，如果使用常规的方式比较大小并从头插入，有可能导致整个数组的后续元素逐一后移，增加时间复杂度，考虑从后往前排序，先放入大的再放入小的，这样可以规避整体移动数组元素的操作消耗。

2.3 时间复杂度

  若两个序列的长度分别为m和n，时间复杂度为O(m + n)。

2.4 空间复杂度

  空间复杂度为O(1)。

3 源码

细节：

1. 从后往前排可以规避数组元素的后移操作。

C++版本：

/**
* @param A: sorted integer array A
* @param B: sorted integer array B
* @return: nothing
*/
void mergeSortedArray(int A[], int m, int B[], int n) {// write your code hereint index = m + n - 1;int i = m - 1;int j = n - 1;while (i >= 0 && j >= 0){if (A[i] > B[j]){A[index--] = A[i--];}else{A[index--] = B[j--];}}while (i >= 0){A[index--] = A[i--];}while (j >= 0){A[index--] = B[j--];}
}