LeetCode Python, Java, C++ > 数组 > 3478. 选出和最大的 K 个元素 > 已支持 Python > GitHub 或 转发
力扣链接：3478. 选出和最大的 K 个元素，难度等级：中等。
给你两个整数数组，nums1 和 nums2，长度均为 n，以及一个正整数 k 。
对从 0 到 n - 1 每个下标 i ，执行下述操作：
- 找出所有满足
nums1[j]小于nums1[i]的下标j。 - 从这些下标对应的
nums2[j]中选出 至多k个，并 最大化 这些值的总和作为结果。
返回一个长度为 n 的数组 answer ，其中 answer[i] 表示对应下标 i 的结果。
示例 1:
输入: nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2
输出: [80,30,0,80,50]
解释:
- 对于
i = 0：满足nums1[j] < nums1[0]的下标为[1, 2, 4]，选出其中值最大的两个，结果为50 + 30 = 80。 - 对于
i = 1：满足nums1[j] < nums1[1]的下标为[2]，只能选择这个值，结果为30。 - 对于
i = 2：不存在满足nums1[j] < nums1[2]的下标，结果为0。 - 对于
i = 3：满足nums1[j] < nums1[3]的下标为[0, 1, 2, 4]，选出其中值最大的两个，结果为50 + 30 = 80。 - 对于
i = 4：满足nums1[j] < nums1[4]的下标为[1, 2]，选出其中值最大的两个，结果为30 + 20 = 50。
示例 2:
输入: nums1 = [2,2,2,2], nums2 = [3,1,2,3], k = 1
输出: [0,0,0,0]
解释:
由于 nums1 中的所有元素相等，不存在满足条件 nums1[j] < nums1[i]，所有位置的结果都是 0 。
约束:
n == nums1.length == nums2.length1 <= n <= 10^51 <= nums1[i], nums2[i] <= 10^61 <= k <= n
提示 1
Sort nums1 and its corresponding nums2 values together based on nums1.
提示 2
Use a max heap to track the top k values of nums2 as you process each element in the sorted order.
思路
站长 (张健)： 👋
大家好！我是张健。
我深知学习算法和找到好工作之间的挑战。因此，除了这个项目，我个人还开发了
leader.me
— 这是程序员打造个人IP的终极平台，包含作品集、简历和博客等。
🚀 掌握算法是基础，而 leader.me 助您完美展示技能，顺利拿到 Offer！
立即前往 leader.me 打造你的程序员专属个人IP →
要求1：找出所有满足
nums1[j]小于nums1[i]的下标j。
看到这个，大家一定会想到把nums1按从小到大排序，这样，前面的小于等于后面的，但一排序下标就乱了。如果对这个问题没有好办法解决，整个题目就做不出来。先请思考下。点击查看答案
在排序时带上索引下标，即排序的对象是元组
(num, index)的数组。这个技术一定要掌握，许多题目都会用到。解决了上面的问题，下标就都有了，我们再看：
要求2：从这些下标对应的
nums2[j]中选出 至多k个，并 最大化 这些值的总和作为结果。看到这个，你想到用什么好方法了吗？
点击查看答案
堆排序，维护一个大小为
k的大根堆。这也是经常考察的知识点，一定要掌握哦。看到这，请你先按上文提示把代码实现一下。
最后，发现还要对连续出现的重复的
num进行特别处理，即相同的num对应的answer中的值应该是一样的。处理方法有多种，怎么处理最简单呢？点击查看答案
用一个
Map，key为num, 相同的key直接使用key对应的值。
复杂度
时间复杂度
O(N * logN)
空间复杂度
O(N)
Python #
class Solution:
def findMaxSum(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
num_index_list = [(num, index) for index, num in enumerate(nums1)] # key 1
num_index_list.sort()
answer = [None] * len(nums1)
k_max_nums = []
sum_ = 0
num_to_sum = defaultdict(int) # key 2
for i, num_index in enumerate(num_index_list):
num, index = num_index
if num in num_to_sum:
answer[index] = num_to_sum[num]
else:
answer[index] = sum_
num_to_sum[num] = sum_
heapq.heappush(k_max_nums, nums2[index])
sum_ += nums2[index]
if len(k_max_nums) > k:
num = heapq.heappop(k_max_nums) # key 3
sum_ -= num
return answer
其它语言
欢迎贡献代码到 LeetCode.blog GitHub -> 3478. 选出和最大的 K 个元素。感谢！打造你的开发者个人IP
🚀 掌握算法是成功的基石，而全方位展示你的才华则是获得垂青的关键。
我的另一个项目 leader.me —— 专为程序员打造的“全能型”个人品牌展示平台。三位一体（All-In-One）的职场利器：
- 📄 简历 + 作品集 + 博客： 将你的 GitHub 项目、技术心得与职场经历完美融合。
- 🌐 永久免费自定义域名： 支持绑定你自己的独立域名，且该功能永久免费。
- ✨ 顶级行业子域名： 提供
name.leader.me—— 极具职业含金量的专属域名。