Leetcode春季活动打卡第三天:面试题 10.01. 合并排序的数组

Leetcode春季活动打卡第三天:面试题 10.01. 合并排序的数组

Leetcode春季活动打卡第三天:面试题 10.01. 合并排序的数组

思路

这道题,两个数组原本就有序。于是我们采用双指针法完成题目。

又由于A本身就预留了足够的空间,于是我们的双指针就逆向执行,即从大到小移动,直接从A数组的最后开始覆盖。这样就不需要引用额外的临时数组。

不用考虑A数组的有效值是否会被覆盖。因为只有当A数组的位置没给够的情况下才会出现覆盖有效值的情况。

Talk is cheap . Show me the code .

class Solution {
public:
void merge(vector<int>& A, int m, vector<int>& B, int n) {
int p=m-1,q=n-1,cnt=A.size()-1;
while(p>=0&&q>=0){
if(A[p]<=B[q]) A[cnt--]=B[q--];
else if(A[p]>B[q]) A[cnt--]=A[p--];
}
while(q>=0) A[cnt--]=B[q--];
while(p>=0) A[cnt--]=A[p--];
}
};
上一篇:《Java程序员面试笔试宝典》之switch使用时有哪些注意事项


下一篇:Java的Exception和Error面试题10问10答