今天参加笔试，遇到一题！求讲解！ - 数据结构与算法

编程论坛 → 开发语言 → 『数据结构与算法』 → 今天参加笔试，遇到一题！求讲解！

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

只看楼主

船长狙击手

来　自：湖北
等　级：新手上路
帖　子：6
专家分：2
注　册：2011-11-27
结帖率：0

楼主

已结贴√ 问题点数：20 回复次数：4

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

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

搜索更多相关主题的帖子: 元素　

2013-05-20 12:15

azzbcc

来　自：江西财经大学
等　级：贵宾
威　望：81
帖　子：3293
专家分：12919
注　册：2012-11-4

第 2 楼

得分:20

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++;
}