一天一道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--];
}
}
};