给你两个按 非递减顺序 排列的整数数组
nums1
和nums2
,另有两个整数m
和n
,分别表示nums1
和nums2
中的元素数目 请你 合并nums2
到nums1
中,使合并后的数组同样按 非递减顺序 排列
最终,合并后数组不应由函数返回,而是存储在数组
nums1
中。为了应对这种情况,nums1
的初始长度为m + n
,其中前m
个元素表示应合并的元素,后n
个元素为0
,应忽略。nums2
的长度为n
nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 -109 <= nums1[i], nums2[j] <= 109
空间复杂度为O(1):即不创建其他数组 时间复杂度为 O(m + n):即一层循环
数组一和数组二一个一个比较,决定放的位置的次序 如果是从前合并则会覆盖数据,从后则不会
参考代码:
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
//记录第一个数组和第二个最后一位有效数据
int end1 = m - 1, end2 = n - 1;
//标记第一个数组的最后位置
int end = m + n - 1;
//有一个小于零则数组越界
while(end1>=0&&end2>=0)
{
if (nums1[end1] >= nums2[end2])
{
//先赋值,后自增
nums1[end--] = nums1[end1--];
}
else
{
nums1[end--] = nums2[end2--];
}
}
//end2越界时,数组一的数据已经在合并数组内且不用处理了
//end1越界时,数组二还有数据未合并
while (end2>=0)
{
nums1[end--] = nums2[end2--];
}
}
执行结果: