2025-09-08：选出和最大的 K 个元素。用go语言，给定两个长度均为 n

热门资讯 2025年09月09日 15:10 1 admin

2025-09-08：选出和最大的 K 个元素。用go语言，给定两个长度均为 n 的整数数组 nums1 和 nums2，以及正整数 k。

对每个位置 i（0 ≤ i < n）进行如下计算：

• 找出所有下标 j（j ≠ i），使得 nums1[j] 的值严格小于 nums1[i]；

• 在这些符合条件的 j 对应的 nums2[j] 值中，最多挑选 k 个，使得被选值的和尽可能大；

• 将能得到的最大和记为 answer[i]。

返回长度为 n 的数组 answer，其中第 i 项为上述计算得到的最大和。

n == nums1.length == nums2.length。

1 <= n <= 100000。

1 <= nums1[i], nums2[i] <= 1000000。

1 <= k <= n。

输入：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 。

题目来自力扣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 < k（即还没有处理够 k 个元素），直接将 y 加入堆（通过赋值给 h.IntSlice[i]），并累加到 s。

• 当 i == k 时，对堆进行初始化（调用 heap.Init(&h)），使其成为合法的最小堆。

• 对于 i >= k 的情况：如果当前元素的 y 值大于堆顶（即当前堆中最小的元素），则用当前 y 替换堆顶，并更新和 s = s + y - 堆顶元素，然后调整堆（调用 heap.Fix(&h, 0)）。

4. 返回答案数组 ans：

• 遍历结束后，ans 数组中的每个位置 i 存储了对于原始下标 i 的答案（即所有 nums1[j] < nums1[i] 的下标 j 中，最大的 k 个 nums2[j] 的和）。

总的时间复杂度和总的额外空间复杂度：

• 时间复杂度：

排序：O(n log n)。
遍历数组：O(n)。
堆操作（初始化、插入、删除等）：每次堆操作的时间复杂度为 O(log k)，最坏情况下进行 O(n) 次堆操作（即每次都需要调整），所以堆操作总时间为 O(n log k)。
总时间复杂度：O(n log n + n log k)。由于 k <= n，可以简化为 O(n log n)。

• 额外空间复杂度：

结构体切片 a：O(n)。
答案数组 ans：O(n)。
堆：O(k)。
总额外空间复杂度：O(n + k)，即 O(n)（因为 k <= n）。

因此，总的时间复杂度为 O(n log n)，总的额外空间复杂度为 O(n)。

Go完整代码如下：

package mainimport (    "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 < k {            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)}

2025-09-08：选出和最大的 K 个元素。用go语言，给定两个长度均为 n

Python完整代码如下：

# -*-coding:utf-8-*-import heapqfrom typing import Listdef 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 < k:            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)