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：
题目来自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))
}