88. Merge Sorted Array

problem description

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.

• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

algorithm thought

合并两个有序数组，这也是归并排序中必不可少的一步，如何做好这一步，速度快并且不溢出，还是有点难度的。我们归并排序的时候，一般是将前半部分数组复制，后半部分数组保存。但是这里是将后半部分数组赋值，前半部分保存下来。我们需要尽可能的利用前面保存的数据，能不改变就不改变。所以我们从后往前合并。如果nums2已经用完了，这时候，nums1前面的数据就能直接使用了，而不需要改变。

code

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=m-1,j=n-1,res=m+n-1;
        while(j>=0){
            nums1[res--]= i>=0&&nums1[i]>nums2[j]?nums1[i--]:nums2[j--];
        }
    }
};

algorithm analysis

对每个数操作一次，时间复杂度O(m+n)