今天参加笔试，遇到一题！求讲解！

船长狙击手发布于 2013-05-20 12:15， 949 次点击

已知两个升序数组均为K个元素 A[K],B[K];已知1《=i，j《=k；求（ai +bj）中最小的K个！要求效率最高！本人思考半天，只能用最笨的方法解出！你们能用什么效率搞得算法解决这道题吗？

4 回复

azzbcc2013-05-20 13:22

int s1[K-1] = {a[1]- a[0], a[2] - a[1]...};
int s2[K-1] = {b[1]- a[0], b[2] - b[1]...};
int ans[K] = {a[0] + b[0]};

for (i = j = 0;i + j < k-1;)
{
    if      (s1[i] > s2[j])  ans[i+j+1] = ans[i+j] + s2[j++];
    else if (s1[i] < s2[j])  ans[i+j+1] = ans[i+j] + s1[i++];
    else    ans[i+j+1] = ans[i+j+2] = ans[i+j] + s1[i++], j++;
}

azzbcc2013-05-20 13:24

求差的过程可以加到循环中，O(n)应该蛮快了吧

azzbcc2013-05-20 15:31

想当然了，额，不对。。。

船长狙击手2013-05-22 12:37

回复 4楼 azzbcc

好厉害啊!我测试了下，果然是对的！而且结果也挺好！敢问大神是怎么分析这道题的？？