【一天一道LeetCode】#88. Merge Sorted Array

一天一道LeetCode

本系列文章已全部上传至我的github,地址:ZeeCoder‘s Github

欢迎大家关注我的新浪微博,我的新浪微博

欢迎转载,转载请注明出处

(一)题目

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 >nums1and nums2 are m and n respectively.

(二)解题

题目大意:给定两个排好序的数组,将后一个数组按序插入到前一个数组。

前面我们做过排序两个已排好序的链表的题:【一天一道LeetCode】#21. Merge Two Sorted Lists可以参考一下做法。

由于是数组,不能按照链表那样随意插入,而题目中已经写明数组1的空间大于等于m+n,所以可以考虑从后往前进行排序。

合并后的数组的大小为m+n,比较两个数组的尾部数,依序从新数组的尾部向前依次填入。

具体细节看代码:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if(n==0) return;
        int i = m-1;
        int j = n-1;
        while(i>=-1&&j>=0)//这里i==-1代表nums1已经比较完了,nums2还有数
        {
            if(i==-1||nums1[i]<nums2[j])nums1[i+j+1] = nums2[j--]; //从数组尾部开始比较,依次填入到新数组的尾部
            else nums1[i+j+1] = nums1[i--];
        }
    }
};

上一篇:C++ 重定义、重载、覆盖


下一篇:[Scala]Scala学习笔记四 类