链接: 合并两个有序数组
这题有个要求:能不能使用O(m+n)的时间复杂度完成?
那当然是有的!
思路:用两个指针分别指向两个数组的尾部!这个很关键! 然后从后向前遍历。又题目可知,nums1的大小肯定是m+n的,且nums1的后半部分是空的,直接覆盖是没影响的。 所以就是将nums2中的元素与nums1中的比较,谁大就先放谁进去。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1=m-1,p2=n-1;
int i=1;
while(p1>=0||p2>=0)
{
if(p1<0)
{
nums1[m+n-i]=nums2[p2];
p2--;
i++;
}
else if(p2<0)
{
break;
}
else if(nums1[p1]<=nums2[p2])
{
nums1[m+n-i]=nums2[p2];
i++;
p2--;
}
else
{
nums1[m+n-i]=nums1[p1];
p1--;
i++;
}
}
}
};