首页 > 代码库 > 第十二题 Merge Sorted Array
第十二题 Merge Sorted Array
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 and nrespectively.
Solution1:新建ArrayList暂存merged list,后放回A
public class Solution { public void merge(int A[], int m, int B[], int n) { int length = m+n; ArrayList<Integer> merge = new ArrayList<Integer>(); int posA =0, posB=0, i=0; while( i<length){ if(posB>=n){merge.add(A[posA]); posA++; i++;} else if(posA>=m){ merge.add(B[posB]); posB++; i++;} else if(A[posA]<=B[posB]){merge.add(A[posA]); posA++; i++;} else{merge.add(B[posB]); posB++; i++;} } for(i=0; i<length;i++){ A[i] = merge.get(i); } } }Solution2:可不能够不额外开辟空间?利用倒序。
public class Solution { public void merge(int A[], int m, int B[], int n) { int position = m+n-1; while(m>0 && n>0){ if(A[m-1]>=B[n-1]) { A[position] = A[m-1]; m--; } else{ A[position] = B[n-1]; n--; } position--; } while(n>0){ A[position] = B[n-1]; n--; position--; } } }
Solution1:再简单点?
public class Solution { public void merge(int A[], int m, int B[], int n) { for(int i=m+n-1; i>=0; i--) A[i]=((m>0)&&(n==0 || A[m-1]>=B[n-1]))?A[--m]:B[--n]; } }
第十二题 Merge Sorted Array
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。