https://www.lintcode.com/problem/merge-two-sorted-arrays/description
描述
合并两个排序的整数数组A和B变成一个新的数组。
样例
给出A=[1,2,3,4],B=[2,4,5,6],返回 [1,2,2,3,4,4,5,6]
挑战
你能否优化你的算法,如果其中一个数组很大而另一个数组很小?
思路
这个算是非常简单了,设立三个索引分别标记来源数组A,B和目标数组当前要处理的元素,取A和B的当前元素值小的赋值给新数组当前元素,然后移动索引。
代码
挑战
挑战部分提到的,两个数组大小差别很大的情况下,提高性能大概只有System.arraycopy了。
改进代码如下:
其实两个System.arraycopy还可以减少为一个。
System.arraycopy((indexA==A.length)?B:A, indexA==A.length?indexB:indexA, t, i, t.length-i);
性能测试代码:
测试结果:
run:
System.arraycopy = 21441659938
成功构建 (总时间: 43 秒)
跑了好几次,效率差异较小,还多次出现过System.arraycopy较慢的情况。
Java性能比较复杂的
领取专属 10元无门槛券
私享最新 技术干货