关关的刷题日记16 – Leetcode 88. Merge Sorted Array

题目

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--; 
        }
    }
};

人生易老，唯有陪伴最长情，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。