好贷网好贷款

Merge Sorted Array -- LeetCode

发布时间:2016-12-4 3:54:26 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Merge Sorted Array -- LeetCode",主要涉及到Merge Sorted Array -- LeetCode方面的内容,对于Merge Sorted Array -- LeetCode感兴趣的同学可以参考一下。

这是一道数组操作的题目,思路比较明确,就是维护三个index,分别对应数组A,数组B,和结果数组。然后A和B同时从后往前扫,每次迭代中A和B指向的元素大的便加入结果数组中,然后index-1,另一个不动。代码如下:  public void merge(int A[], int m, int B[], int n) { if(A==null || B==null) return; int idx1 = m-1; int idx2 = n-1; int len = m+n-1; while(idx1>=0 && idx2>=0) { if(A[idx1]>B[idx2]) { A[len--] = A[idx1--]; } else { A[len--] = B[idx2--]; } } while(idx2>=0) { A[len--] = B[idx2--]; } }这里从后往前扫是因为这个题目中结果仍然放在A中,如果从前扫会有覆盖掉未检查的元素的可能性。算法的时间复杂度是O(m+n),m和n分别是两个数组的长度,空间复杂度是O(1)。这个题类似的有Merge Two Sorted Lists,只是后者是对于LinkedList操作,面试中可能会一起问到。

上一篇:杨辉三角(两个一维数组)
下一篇:义工简讯-10月15日国际盲人日,钟…

相关文章

相关评论