【题目】
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m andn respectively.
【分析】
无
【代码】
/********************************* * 日期:2015-01-05 * 作者:SJF0115 * 题目: 88.Merge Sorted Array * 来源:https://oj.leetcode.com/problems/merge-sorted-array/ * 结果:AC * 来源:LeetCode * 博客: **********************************/ #include <iostream> using namespace std; class Solution { public: void merge(int A[], int m, int B[], int n) { if(n <= 0){ return; }//if int indexA = 0,indexB = 0; while(indexA < m && indexB < n){ // B数组元素插入A数组中 if(A[indexA] >= B[indexB]){ // 后移一位 for(int i = m-1;i >= indexA;i--){ A[i+1] = A[i]; }//for A[indexA] = B[indexB]; m++; indexB++; }//if indexA++; }//while // 如果B数组还没有遍历完 while(indexB < n){ A[indexA++] = B[indexB++]; }//while } }; int main() { Solution solution; int A[] = {1,2,4,7,9}; int B[] = {3,5,8,10,11,12}; int m = 5; int n = 6; solution.merge(A,m,B,n); // 输出 for(int i = 0;i < 11;i++){ cout<<A[i]<<" "; } cout<<endl; }
【代码二】
The idea is to go from the last indexes of both arrays, compare and put elements from either A or B to the final position, which can easily get since we know that A have enough space to store them all and we know size of A and B. Please refer to the comments for details.
/********************************* * 日期:2015-01-05 * 作者:SJF0115 * 题目: 88.Merge Sorted Array * 来源:https://oj.leetcode.com/problems/merge-sorted-array/ * 结果:AC * 来源:LeetCode * 博客: **********************************/ #include <iostream> using namespace std; class Solution { public: void merge(int A[], int m, int B[], int n) { if(n <= 0){ return; }//if int indexA = m-1,indexB = n-1,cur = m + n -1; // AB数组从后往前扫描 while(indexA >= 0 && indexB >= 0){ if(A[indexA] < B[indexB]){ A[cur--] = B[indexB--]; }//if else{ A[cur--] = A[indexA--]; }//else }//while // 如果B数组没有遍历完 while(indexB >= 0){ A[cur--] = B[indexB--]; }//while } }; int main() { Solution solution; int A[] = {1,2,4,7,9}; int B[] = {3,5,8,10,11,12}; int m = 5; int n = 6; solution.merge(A,m,B,n); // 输出 for(int i = 0;i < 11;i++){ cout<<A[i]<<" "; } cout<<endl; }