2024-10-23：最高频率的 ID。用go语言，给定两个长度相等的整数数组 nums 和 freq，

其中nums中的每个元素表示一个ID，

而freq中的每个元素表示对应ID在此次操作后出现的次数变化。

如果freq[i]为正数，则表示在这次操作中nums[i]的ID会增加freq[i]次；

如果freq[i]为负数，则表示在这次操作中nums[i]的ID会减少-freq[i]次。

输出一个长度为n的数组ans，其中ans[i]表示第i步操作后出现频率最高的ID的数目。

若集合在某次操作后为空，则ans[i]为0。

输入：nums = [2,3,2,1], freq = [3,2,-3,1]。

输出：[3,3,2,2]。

解释：

第 0 步操作后，有 3 个 ID 为 2 的元素，所以 ans[0] = 3 。

第 1 步操作后，有 3 个 ID 为 2 的元素和 2 个 ID 为 3 的元素，所以 ans[1] = 3 。

第 2 步操作后，有 2 个 ID 为 3 的元素，所以 ans[2] = 2 。

第 3 步操作后，有 2 个 ID 为 3 的元素和 1 个 ID 为 1 的元素，所以 ans[3] = 2 。

答案2024-10-23：

chatgpt

题目来自leetcode3092。

大体步骤如下：

1.初始化一个空的 map[int]int，用于记录每个 ID 在每次操作后的出现次数变化。

2.初始化一个空的最大堆 hp，用于存储每个 ID 的出现次数。

3.循环遍历 nums 数组以及对应的 freq 数组，对于每个元素：

• 将该 ID 出现的次数变化加到 ID 对应的计数器中。

• 创建一个 pair 结构，记录 ID 和其出现次数。

• 将该 pair 推入最大堆 hp 中。

• 检查堆顶元素是否仍然对应堆顶 ID 的实际计数，如果不是，则从堆中移除堆顶，直到堆顶元素的计数与实际计数一致。

• 将当前步骤中最高频率的 ID 的数目记录在答案数组 ans 中。

4.返回生成的 ans 数组。

总的时间复杂度为 O(n log n)，其中 n 是数组的长度，因为在最坏情况下，我们可能需要对堆进行 n 次插入和弹出操作，每次操作的时间复杂度为 log n。

额外空间复杂度为 O(n)，主要是用于存储 ans 数组和堆 hp，以及辅助的计数器 cnt。

Go完整代码如下：

package main

import (
	"fmt"
	"container/heap"
)

func mostFrequentIDs(nums, freq []int) []int64 {
	ans := make([]int64, len(nums))
	cnt := make(map[int]int)
	h := hp{}
	heap.Init(&h)
	for i, x := range nums {
		cnt[x] += freq[i]
		heap.Push(&h, pair{cnt[x], x})
		for h[0].c != cnt[h[0].x] { // 堆顶保存的数据已经发生变化
			heap.Pop(&h) // 删除
		}
		ans[i] = int64(h[0].c)
	}
	return ans
}

type pair struct{ c, x int }
type hp []pair
func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].c > h[j].c } // 最大堆
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }


func main() {
	nums := []int{2,3,2,1}
	freq := []int{3,2,-3,1}
	fmt.Println(mostFrequentIDs(nums,freq))
}