88.md

#88. Merge Sorted Array 题目链接

void merge(int* nums1, int m, int* nums2, int n)
{
    int b = 0;
    int i = 0;
    int j = 0;
    for (i; i < n && b < m + i; b++)
    {
        if (nums2[i] < nums1[b])
        {
            for (j = m + i; j > b; j--)
            {
                nums1[j] = nums1[j-1];
            }
            nums1[b] = nums2[i];
            i++;
        }
    }
    for(i; i < n; i++)
    {
        nums1[b] = nums2[i];
        b++;
    }
}

用最暴力的方法，每当nums2数组中有一个数小于nums中的数时，把之后的数字向后移一位，并把nums2中的数字插入到当前位置中。改时间复杂为O(n)

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

这种方法的时间复杂度只有O(n)，该算法从后向前构造nums1数组，因为num1数组后面是空的，所以不会有覆盖的情况，而且前面覆盖的时候，被覆盖的值已经填充的数组的尾部了，该算法省去了数组内元素移动的时间