力扣刷题——面试经典150道—1.合并两个有序数组（题目88）

题目要求：时间复杂度m+n

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int i=nums1Size-1;
    int l1=m-1,l2=n-1;

    for(;l1>=0&&l2>=0;i--){
        if(nums1[l1]>=nums2[l2]){
            nums1[i]=nums1[l1];
            l1--;
        }else{
            nums1[i]=nums2[l2];
            l2--;
        }
    }

    if(l1>=0){
        for(;l1>=0;i--){
            nums1[i]=nums1[l1];
            l1--;
        }
    }
    if(l2>=0){
        for(;l2>=0;i--){
            nums1[i]=nums2[l2];
            l2--;
        }
    }
}

本来打算将nums1复制到新数组中后排序，但复制数组最低需要遍历，时间复杂度太高

通过使用nums1后半部分的空闲位置来进行逆排序，使得时间复杂度为m+n

但比较方法存在一些问题，使得运行时间为8ms

2点改进：

? ? ? ? 1、当m为0时，直接复制数组，然后返回

? ? ? ? 2、当一数组中存在比二数组中最小的更小的数字时，不需要管

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int i=nums1Size-1;
    int l1=m-1,l2=n-1;

    if(m=0){
        for(;l2>=0;i--){
            nums1[i]=nums2[l2];
            l2--;
        }
        return;
    }

    for(;l1>=0&&l2>=0;i--){
        if(nums1[l1]>=nums2[l2]){
            nums1[i]=nums1[l1];
            l1--;
        }else{
            nums1[i]=nums2[l2];
            l2--;
        }
    }

    if(l2>=0){
        for(;l2>=0;i--){
            nums1[i]=nums2[l2];
            l2--;
        }
    }
}