Medium

题目描述

该问题涉及跟踪在一个随时间变化的集合中 ID 的频率。你有两个长度为 n 的整数数组 nums 和 freq。nums 中的每个元素表示一个 ID，freq 中对应的元素表示在每一步中应该向集合添加或从集合中删除该 ID 的次数。

  • 添加 ID：如果 freq[i] 是正数，表示在第 i 步向集合中添加 freq[i] 个值为 nums[i] 的 ID。
  • 删除 ID：如果 freq[i] 是负数，表示在第 i 步从集合中删除 -freq[i] 个值为 nums[i] 的 ID。

返回一个长度为 n 的数组 ans，其中 ans[i] 表示在第 i 步之后集合中最频繁 ID 的数量。如果在任何步骤中集合为空，则该步骤的 ans[i] 应为 0。

示例 1：

输入：nums = [2,3,2,1], freq = [3,2,-3,1]
输出：[3,3,2,2]
解释：
在步骤 0 之后，我们有 3 个值为 2 的 ID。所以 ans[0] = 3。
在步骤 1 之后，我们有 3 个值为 2 的 ID 和 2 个值为 3 的 ID。所以 ans[1] = 3。
在步骤 2 之后，我们有 2 个值为 3 的 ID。所以 ans[2] = 2。
在步骤 3 之后，我们有 2 个值为 3 的 ID 和 1 个值为 1 的 ID。所以 ans[3] = 2。

示例 2：

输入：nums = [5,5,3], freq = [2,-2,1]
输出：[2,0,1]
解释：
在步骤 0 之后，我们有 2 个值为 5 的 ID。所以 ans[0] = 2。
在步骤 1 之后，没有 ID。所以 ans[1] = 0。
在步骤 2 之后，我们有 1 个值为 3 的 ID。所以 ans[2] = 1。

约束条件：

  • 1 <= nums.length == freq.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • -10^5 <= freq[i] <= 10^5
  • freq[i] != 0
  • 输入保证在任何步骤中 ID 的出现次数不会为负数。

解题思路

这道题需要在每一步操作后快速找到最大频次。我们需要维护两个核心数据结构：

主要思路：

  1. 使用哈希表记录每个 ID 的当前频次
  2. 使用优先队列（最大堆）或有序集合维护所有频次值，以快速获取最大值

关键难点：

  • 当某个 ID 的频次发生变化时，需要更新最大频次
  • 删除操作可能使某些 ID 的频次变为 0，需要从频次集合中移除
  • 需要处理重复频次值的情况

推荐解法：使用优先队列 + 懒删除

  • 用哈希表 count 记录每个 ID 的真实频次
  • 用最大堆 maxHeap 维护所有频次值
  • 在获取最大值时，检查堆顶元素是否仍然有效（懒删除策略）

优化方案： 由于可能存在大量的无效频次值在堆中，我们采用懒删除：只有在查询最大值时才清理无效元素，避免频繁的堆操作，提高效率。

这种方法既保证了正确性，又在大多数情况下具有良好的性能表现。

代码实现

class Solution {
public:
    vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {
        int n = nums.size();
        vector<long long> ans(n);
        unordered_map<int, long long> count;
        priority_queue<long long> maxHeap;
        
        for (int i = 0; i < n; i++) {
            count[nums[i]] += freq[i];
            if (count[nums[i]] == 0) {
                count.erase(nums[i]);
            }
            
            maxHeap.push(count[nums[i]]);
            
            // Clean up invalid frequencies
            while (!maxHeap.empty()) {
                long long maxFreq = maxHeap.top();
                bool found = false;
                for (auto& p : count) {
                    if (p.second == maxFreq) {
                        found = true;
                        break;
                    }
                }
                if (found) {
                    ans[i] = maxFreq;
                    break;
                } else {
                    maxHeap.pop();
                }
            }
            
            if (maxHeap.empty()) {
                ans[i] = 0;
            }
        }
        
        return ans;
    }
};

class Solution:
    def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        count = {}
        max_heap = []
        
        for i in range(n):
            if nums[i] in count:
                count[nums[i]] += freq[i]
            else:
                count[nums[i]] = freq[i]
            
            if count[nums[i]] == 0:
                del count[nums[i]]
            
            if nums[i] in count:
                heapq.heappush(max_heap, -count[nums[i]])
            
            # Clean up invalid frequencies
            while max_heap:
                max_freq = -max_heap[0]
                if max_freq in count.values():
                    ans[i] = max_freq
                    break
                else:
                    heapq.heappop(max_heap)
            
            if not max_heap:
                ans[i] = 0
        
        return ans

public class Solution {
    public long[] MostFrequentIDs(int[] nums, int[] freq) {
        int n = nums.Length;
        long[] ans = new long[n];
        Dictionary<int, long> count = new Dictionary<int, long>();
        PriorityQueue<long, long> maxHeap = new PriorityQueue<long, long>(Comparer<long>.Create((x, y) => y.CompareTo(x)));
        
        for (int i = 0; i < n; i++) {
            if (count.ContainsKey(nums[i])) {
                count[nums[i]] += freq[i];
            } else {
                count[nums[i]] = freq[i];
            }
            
            if (count[nums[i]] == 0) {
                count.Remove(nums[i]);
            }
            
            if (count.ContainsKey(nums[i])) {
                maxHeap.Enqueue(count[nums[i]], count[nums[i]]);
            }
            
            // Clean up invalid frequencies
            while (maxHeap.Count > 0) {
                long maxFreq = maxHeap.Peek();
                bool found = false;
                foreach (var value in count.Values) {
                    if (value == maxFreq) {
                        found = true;
                        break;
                    }
                }
                if (found) {
                    ans[i] = maxFreq;
                    break;
                } else {
                    maxHeap.Dequeue();
                }
            }
            
            if (maxHeap.Count == 0) {
                ans[i] = 0;
            }
        }
        
        return ans;
    }
}

var mostFrequentIDs = function(nums, freq) {
    const countMap = new Map();
    const freqCount = new Map();
    const result = [];
    let maxFreq = 0;
    
    for (let i = 0; i < nums.length; i++) {
        const id = nums[i];
        const change = freq[i];
        
        // Remove old frequency count
        const oldCount = countMap.get(id) || 0;
        if (oldCount > 0) {
            freqCount.set(oldCount, (freqCount.get(oldCount) || 0) - 1);
            if (freqCount.get(oldCount) === 0) {
                freqCount.delete(oldCount);
            }
        }
        
        // Update ID count
        const newCount = oldCount + change;
        if (newCount > 0) {
            countMap.set(id, newCount);
            freqCount.set(newCount, (freqCount.get(newCount) || 0) + 1);
        } else {
            countMap.delete(id);
        }
        
        // Find max frequency
        maxFreq = 0;
        for (const freq of freqCount.keys()) {
            maxFreq = Math.max(maxFreq, freq);
        }
        
        result.push(maxFreq);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
优先队列 + 懒删除O(n log n)O(n)

时间复杂度分析：

  • 每次操作需要向堆中插入元素：O(log n)
  • 懒删除过程中最坏情况下需要检查所有堆元素：O(n log n)
  • 总体时间复杂度：O(n log n)

空间复杂度分析：

  • 哈希表存储 ID 计数：O(n)
  • 优先队列存储频次值：O(n)
  • 总体空间复杂度：O(n)