Leetcode-88：合并两个有序数组
题目链接
法一：
逐个比较，逐个移动
时间复杂度：O(n^2)
空间复杂度：O(1)
法二：
双指针遍历，借助一个额外空间，先利用双指针将排序结果存于该空间，后用for循环逐个移至原数组
时间复杂度：O(n)
空间复杂度：O(n)
法三：
倒序遍历，从数组尾部开始，先安插较大的数值，避免每次插入操作需要移动其他元素位置，且所有操作都在原数组上进行，不需要借助额外空间
时间复杂度：O(n)
空间复杂度：O(1)
C代码
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int p1 = m-1, p2 = n-1,i=nums1Size-1;while(i!=-1) {if(p2<0 || (p1>=0 && nums1[p1] > nums2[p2])) nums1[i] = nums1[p1--];else nums1[i] = nums2[p2--];i--;}
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！