数组相关面试题--5.合并两个有序数组
5. 合并两个有序数组
88. 合并两个有序数组 - 力扣(LeetCode)
解题思路:1. 从后往前遍历数组,将nums1和nums2中的元素逐个比较将较大的元素往nums1末尾进行搬移2. 第一步结束后,nums2中可能会有数据没有搬移完,将nums2中剩余的元素逐个搬移到nums1时间复杂度:O(m+n)空间复杂度: O(1)
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){// end1、end2:分别标记nums1 和 nums2最后一个有效元素位置// end标记nums1的末尾,因为nums1和nums2中的元素从后往前往nums1中存放// ,否则会存在数据覆盖int end1 = m-1;int end2 = n-1;int index = m+n-1;// 从后往前遍历,将num1或者nums2中较大的元素往num1中end位置搬移// 直到将num1或者num2中有效元素全部搬移完while(end1 >= 0 && end2 >= 0){if(nums1[end1] > nums2[end2]){nums1[index--] = nums1[end1--];}else{nums1[index--] = nums2[end2--];}}// num2中的元素可能没有搬移完,将剩余的元素继续往nums1中搬移while(end2 >= 0){nums1[index--] = nums2[end2--];}// num1中剩余元素没有搬移完 ---不用管了,因为num1中剩余的元素本来就在num1中
}