算法:6.合并排序数组 II

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性能比较复杂的

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180715G1EN5100?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券