2025-09-08：选出和最大的 K 个元素。用go语言炒股配资配资平台，给定两个长度均为 n 的整数数组 nums1 和 nums2，以及正整数 k。
对每个位置 i（0 ≤ i
• 找出所有下标 j（j ≠ i），使得 nums1[j] 的值严格小于 nums1[i]；
• 在这些符合条件的 j 对应的 nums2[j] 值中，最多挑选 k 个，使得被选值的和尽可能大；
• 将能得到的最大和记为 answer[i]。
返回长度为 n 的数组 answer，其中第 i 项为上述计算得到的最大和。
n == nums1.length == nums2.length。
1
1
1
输入：nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2。
输出：[80,30,0,80,50]。
解释：
对于 i = 0 ：满足 nums1[j]
对于 i = 1 ：满足 nums1[j]
对于 i = 2 ：不存在满足 nums1[j]
对于 i = 3 ：满足 nums1[j]
对于 i = 4 ：满足 nums1[j]
题目来自力扣3478。
分步骤详细过程：
1. 初始化与数据结构准备：
• 创建一个长度为 n 的结构体切片 a，每个元素是一个三元组 (x, y, i)，其中 x 是 nums1[i]，y 是 nums2[i]，i 是原始下标。
• 使用 slices.SortFunc 对切片 a 按照 x（即 nums1 的值）进行升序排序。这样，所有元素将按照 nums1 的值从小到大排列。
2. 处理排序后的数组：
• 初始化一个长度为 n 的 ans 数组（类型为 []int64），用于存储每个位置 i 的答案。
• 创建一个最小堆 h（使用 container/heap 包实现），其底层是一个长度为 k 的整数切片，用于维护当前已处理的元素中最大的 k 个 nums2 值。
• 初始化变量 s 为 0，用于记录当前堆中 k 个元素的和。
3. 遍历排序后的数组 a：
• 对于每个索引 i（从0到n-1），取出当前三元组 t = (x, y, i)。
• 处理重复的 x 值：如果当前元素的x值与上一个元素的x值相同（即t.x == a[i-1].x），则直接使用上一个元素的答案（因为相同nums1值的元素，其符合条件的下标集合相同，但注意题目要求严格小于，所以相同值的下标不会相互包含？但这里实际上相同值的下标不会相互满足条件（因为严格小于），但代码中为了优化，直接复用了上一个相同x的答案？这里需要谨慎：实际上，相同nums1值的元素，在计算答案时，彼此之间不会满足条件（因为需要严格小于），所以它们的答案确实相同？但注意：当x相同时，它们都不会出现在对方的候选集合中（因为要求严格小于），但候选集合是相同的（都是所有严格小于x的元素）。因此，对于相同x的元素，其答案确实相同。所以代码直接复用上一个相同x 的答案。
• 如果当前 x是新的（不与前一个相同），则设置ans[t.i] = int64(s)，即当前堆中k个元素的和（但注意：这个s是处理到当前元素之前的所有小于当前x的元素中最大的k个nums2的和？实际上，由于数组按x升序排列，当前元素之前的元素都是x值小于当前元素的（因为严格升序？但可能有重复？实际上排序后相同x是相邻的，所以当前元素之前的元素（除了相同x的）都是严格小于当前x的）。因此，s确实代表了所有严格小于当前x的元素中最大的k个nums2 值的和。
• 维护堆：
• 如果当前索引 i
• 对于 i >= k 的情况：如果当前元素的 y 值大于堆顶（即当前堆中最小的元素），则用当前 y 替换堆顶，并更新和 s = s + y - 堆顶元素，然后调整堆（调用 heap.Fix(&h, 0)）。
4. 返回答案数组 ans：
• 遍历结束后，ans 数组中的每个位置 i 存储了对于原始下标 i 的答案（即所有 nums1[j]
总的时间复杂度和总的额外空间复杂度：
• 时间复杂度：
排序：O(n log n)。
遍历数组：O(n)。
堆操作（初始化、插入、删除等）：每次堆操作的时间复杂度为 O(log k)，最坏情况下进行 O(n) 次堆操作（即每次都需要调整），所以堆操作总时间为 O(n log k)。
总时间复杂度：O(n log n + n log k)。由于 k
• 额外空间复杂度：
结构体切片 a：O(n)。
答案数组 ans：O(n)。
堆：O(k)。
总额外空间复杂度：O(n + k)，即 O(n)（因为 k
因此，总的时间复杂度为 O(n log n)，总的额外空间复杂度为 O(n)。
Go完整代码如下：
package main
import (
"container/heap"
"fmt"
"slices"
"sort"
)
func findMaxSum(nums1, nums2 []int, k int) []int64 {
n := len(nums1)
type tuple struct{ x, y, i int }
a := make([]tuple, n)
for i, x := range nums1 {
a[i] = tuple{x, nums2[i], i}
}
slices.SortFunc(a, func(p, q tuple)int { return p.x - q.x })
ans := make([]int64, n)
h := hp{make([]int, k)}
s := 0
for i, t := range a {
if i > 0 && t.x == a[i-1].x {
ans[t.i] = ans[a[i-1].i]
} else {
ans[t.i] = int64(s)
}
y := t.y
if i
s += y
h.IntSlice[i] = y
continue
}
if i == k {
heap.Init(&h)
}
if y > h.IntSlice[0] {
s += y - h.IntSlice[0]
h.IntSlice[0] = y
heap.Fix(&h, 0)
}
}
return ans
}
type hp struct{ sort.IntSlice }
func (hp) Push(any) {}
func (hp) Pop (_ any) { return }
func main {
nums1 := []int{4, 2, 1, 5, 3}
nums2 := []int{10, 20, 30, 40, 50}
k := 2
result := findMaxSum(nums1, nums2, k)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
import heapq
from typing import List
def findMaxSum(nums1: List[int], nums2: List[int], k: int) -> List[int]:
n = len(nums1)
# 创建元组列表 (nums1[i], nums2[i], i)
a = [(x, nums2[i], i) for i, x in enumerate(nums1)]
a.sort(key=lambda x: x[0])
ans = [0] * n
h = [] # 最小堆
s = 0
for i, (x, y, idx) in enumerate(a):
if i > 0 and x == a[i-1][0]:
# 如果当前nums1值与上一个相同，直接使用上一个的结果
ans[idx] = ans[a[i-1][2]]
else:
ans[idx] = s
if i
s += y
heapq.heappush(h, y)
else:
if y > h[0]:
# 替换堆中最小的元素
s += y - h[0]
heapq.heapreplace(h, y)
return ans
# 测试代码
if __name__ == "__main__":
nums1 = [4, 2, 1, 5, 3]
nums2 = [10, 20, 30, 40, 50]
k = 2
result = findMaxSum(nums1, nums2, k)
print(result)
·
我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。
欢迎关注“福大大架构师每日一题”炒股配资配资平台，让 Go 语言和算法助力您的职业发展
百川资本提示：文章来自网络，不代表本站观点。
相关文章
沪深京指数
热点资讯
