两个有序数组，A[k]和B[k]长度都为k。求前k个最小的(a[i]+b[j])

本文主要是介绍两个有序数组，A[k]和B[k]长度都为k。求前k个最小的(a[i]+b[j])，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

设A={A1,A2,A3,A4,A5,A6,.......} ，B={B1,B2,B3,B4,B5,B6,.......}

因为A和B都是有序的数组，必须充分的利用这点，可能有同学，看到有同学觉得这个题目比较容易，直接将所有的组合都计算出来，然后取最小的K个，其实出题的人是要大家考虑这道题的时间复查度，上面的解法的时间复杂度为o(n2)，出题的人的目的是要时间复杂度最小。

 

下面分析如下：

 

因为A和B都是有序的数组，那么最小的那个肯定是a[0]+b[0]，举例如下:

A={1,2,4,7,9}

B={2,3,6,8,10}

 

第一个：

1+2=3；

1+3=4;

2+2=4;

2+3=5;

4+2=6;

1+6=7；

4+3=7；

2+6=8；

1+8=9；

7+2=9；

 

 

第一个数：

a[0]+b[0]，

 

第2个数为A2-A1，和B2-B1中最小的那一边的数；

 

这篇关于两个有序数组，A[k]和B[k]长度都为k。求前k个最小的(a[i]+b[j])的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---