题解 | #最高售价的两只牛#
最高售价的两只牛
https://www.nowcoder.com/practice/8e4a09d5f63d4298a8507decf5d12490
- 题目考察的知识点 : 贪心算法
- 题目解答方法的文字分析:
- 创建一个最小堆
minHeap
,用于存储每个牛对的负总价值,并保持它们按照降序排列。因为 Python 的默认是最小堆,所以在加入时将其取负号。 - 对于列表
pricesA
中的每个元素和列表pricesB
中的每个元素进行组合,并计算其总价值。将每个牛对和其总价值添加到最小堆minHeap
中。因为我们要找到最大利润的前k
对牛,所以在插入最小堆时可以用负数代替正数。 - 从
minHeap
中弹出当前总价值最大的前k
对牛,并将它们添加到结果列表res
中。由于minHeap
中保存的是负数,因此在弹出元素时需要先将它们取负号
- 本题解析所用的编程语言: Python
- 完整且正确的编程代码
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param pricesA int整型一维数组 # @param pricesB int整型一维数组 # @param k int整型 # @return int整型二维数组 # import heapq class Solution: def kPairsWithLargestSums( self, pricesA: List[int], pricesB: List[int], k: int ) -> List[List[int]]: m, n = len(pricesA), len(pricesB) minHeap = [] # 维护当前总价格最大的k对牛(最小堆) # 将A牛的价格和B牛的价格两两组合,并计算每对牛的总价格,然后将其加入minHeap(按总价格升序排序) for i in range(m): for j in range(n): heapq.heappush(minHeap, (-(pricesA[i] + pricesB[j]), -pricesA[i], -pricesB[j])) # 从minHeap中选择当前总价格最大的牛对,并将其加入res res = [] count = 0 while minHeap and count < k: _, priceA, priceB = heapq.heappop(minHeap) res.append([-priceA, -priceB]) count += 1 return res
牛客高频top202题解系列 文章被收录于专栏
记录刷牛客高频202题的解法思路