两个有序数组间相加和的Topk问题

[编程题]两个有序数组间相加和的Topk问题

热度指数：3470 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个有序数组arr1和arr2，再给定一个整数k，返回来自arr1和arr2的两个数相加和最大的前k个，两个数必须分别来自两个数组

按照降序输出

[要求]

时间复杂度为 $O(k \log k)$

输入描述:

第一行三个整数N, K分别表示数组arr1, arr2的大小，以及需要询问的数
接下来一行N个整数，表示arr1内的元素
再接下来一行N个整数，表示arr2内的元素

输出描述:

输出K个整数表示答案

示例1

输入

5 4
1 2 3 4 5
3 5 7 9 11

输出

16 15 14 14

备注:


保证

算法知识视频讲解

jggnice

发表于 2023-03-07 21:42:58

import sys import heapq as hq from collections import defaultdict, Counter dd = defaultdict(list) cter = Counter() q = [] n, k = [int(c) for c in inpu 展开全文

逆臣可以改

发表于 2022-02-07 23:44:38

建立信息节点Node，存放两个数组中取用的下标和累加值。建立大根堆，维护Node，按照累加值大到小存放。使用HashSet维护Node的访问标记。每次从堆中弹出Node时，取出两个数组中的下标位置，分别看看各自向前移动一个的累加和大小，形成新的节点，再入大根堆，直到满足弹出k个。 impor 展开全文