【LeetCode算法】第88题：合并两个有序数组

目录

一、题目描述

二、初次解答

三、官方解法

四、总结

一、题目描述

二、初次解答

1. 思路：首次想到的解法：定义一个m+n长度的辅助数组，从头遍历这两个数组，谁小就放进辅助数组中并且对应往后走，最后使用memcpy函数将辅助数组内容拷贝到nums1中。这种解法容易想到，但是空间复杂度为O(m+n)。其次想到的解法：定义三个指针i,j,k，其中i指向nums1末尾的有效位，j指向nums2的末尾，k指向nums1的m+n-1位置。循环比较nums1[i]和nums2[j]的大小，谁大就拷贝至nums1[k]并且对应指针-1。当退出循环后，将两个数组中剩下的元素依次拷贝至nums1[k]中。

2. 代码：对应上面的第二种解法。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int temp[m+n];
    int i=m-1,j=n-1,k=nums1Size-1;
    while(j>=0 && i>=0){
        if(nums2[j]>=nums1[i]){
            nums1[k--]=nums2[j--];
        }else{
            nums1[k--]=nums1[i--];
        }
    }
    while(i>=0)
        nums1[k--]=nums1[i--];
    while(j>=0)
        nums1[k--]=nums2[j--];
}

3. 优点：空间复杂度为O(1)且时间复杂度为O(m+n)。

4. 缺点：速度依旧不够快。

三、官方解法

官方解法二和三分别对应上述我想到的第一种解法和第二种解法。官方解法一直接采用合并后排序的方法，调用了qsort函数。

四、总结

合并两个有序数组，可以使用双指针法从后往前遍历，并将元素拷贝至目标位置。