【专知-关关的刷题日记16】Leetcode 88. Merge Sorted Array- 专知

【专知-关关的刷题日记16】Leetcode 88. Merge Sorted Array

点击上方“专知”关注获取更多AI知识!

题目

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

Note:You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

题目的意思是给定两个排好序的数组，要求将这两个数组合并成一个排好序的数组。

方法

思路：因为题目中给定的两个数组是排好序的，所以想到用归并的方法同时从头至尾遍历两个数组，每次将较小的元素放到一个新的数组中，但是这样需要额外开辟新的空间。题目中说nums1的空间是足够大的，所以最好是在原来的nums1上直接操作，因此想到从后往前同时遍历两个数组，后面的元素也挤不到前面的元素，就可以实现不需要额外开辟空间，时间复杂度为O(n)的算法了。写程序的过程中注意当nums1到头的时候，需要把nums2剩下的部分都直接搬到nums1的前面，否则算法功能还没执行完，程序就直接退出了。



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