What is the main challenge in solving the Most Frequent IDs problem?

The main challenge is efficiently tracking the most frequent ID after each update, especially when the collection changes frequently. Using hash maps or ordered sets can help.

How does the frequency change affect the solution?

The frequency change, whether positive or negative, determines how the IDs are added or removed from the collection. This directly impacts the most frequent ID count.

What data structures are best for solving Most Frequent IDs?

Hash maps are great for storing frequency counts, while ordered sets or priority queues are useful for efficiently retrieving the most frequent ID.

How can I optimize my solution for time complexity?

To optimize time complexity, maintain frequency counts in an ordered data structure like a priority queue, which allows efficient retrieval of the most frequent ID.

What happens if the collection becomes empty?

If the collection becomes empty after a step, the result for that step should be 0. This case needs to be handled explicitly during frequency updates.

#3092

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

最高频率的 ID

你需要在一个集合里动态记录 ID 的出现频率。给你两个长度都为 n 的整数数组 nums 和 freq ， nums 中每一个元素表示一个 ID ，对应的 freq 中的元素表示这个 ID 在集合中此次操作后需要增加或者减少的数目。增加 ID 的数目：如果 freq[i] 是正数，那么 freq…

数组哈希表堆（优先队列）有序集合

题目描述

你需要在一个集合里动态记录 ID 的出现频率。给你两个长度都为 n 的整数数组 nums 和 freq ，nums 中每一个元素表示一个 ID ，对应的 freq 中的元素表示这个 ID 在集合中此次操作后需要增加或者减少的数目。

增加 ID 的数目：如果 freq[i] 是正数，那么 freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会添加到集合中。
减少 ID 的数目：如果 freq[i] 是负数，那么 -freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会从集合中删除。

请你返回一个长度为 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 个 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 。

示例 2：

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

输出：[2,0,1]

解释：

第 0 步操作后，有 2 个 ID 为 5 的元素，所以 ans[0] = 2 。
第 1 步操作后，集合中没有任何元素，所以 ans[1] = 0 。
第 2 步操作后，有 1 个 ID 为 3 的元素，所以 ans[2] = 1 。

提示：

1 <= nums.length == freq.length <= 10⁵
1 <= nums[i] <= 10⁵
-10⁵ <= freq[i] <= 10⁵
freq[i] != 0
输入保证任何操作后，集合中的元素出现次数不会为负数。

lightbulb

解题思路

方法一：哈希表 + 优先队列（大根堆）

我们用一个哈希表 $cnt$ 来记录每个 ID 的出现次数，用一个哈希表 $lazy$ 来记录每个次数需要被删除的个数。用一个优先队列 $pq$ 来维护出现次数的最大值。

每一次操作 $(x, f)$ ，我们需要更新 $x$ 的出现次数 $cnt[x]$ ，这意味着 $cnt[x]$ 在 $lazy$ 中的值需要增加 $1$ ，表示该次数需要删除的个数增加 $1$ 。然后我们更新 $cnt[x]$ 的值，将 $cnt[x]$ 加上 $f$ 。然后我们更新后的 $cnt[x]$ 的值加入优先队列 $pq$ 中。然后我们检查优先队列 $pq$ 的堆顶元素，如果 $lazy$ 中对应的次数需要删除的个数大于 $0$ ，我们就将堆顶元素弹出。最后，我们判断优先队列是否为空，如果不为空，堆顶元素就是出现次数的最大值，我们将其加入答案数组中。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]:
        cnt = Counter()
        lazy = Counter()
        ans = []
        pq = []
        for x, f in zip(nums, freq):
            lazy[cnt[x]] += 1
            cnt[x] += f
            heappush(pq, -cnt[x])
            while pq and lazy[-pq[0]] > 0:
                lazy[-pq[0]] -= 1
                heappop(pq)
            ans.append(0 if not pq else -pq[0])
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests if the candidate can efficiently track changes in a dynamic collection.
question_mark
Evaluates the candidate's ability to optimize frequent ID retrieval with advanced data structures.
question_mark
Assesses knowledge of balancing time and space complexity in array-based problems.

warning

常见陷阱

外企场景

error
Not handling the case where the collection becomes empty and the result should be 0.
error
Using inefficient data structures that cause unnecessary time complexity for frequent ID retrieval.
error
Overcomplicating the solution when a simpler hash map or ordered set approach would suffice.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Tracking the most frequent ID in a dynamic stream of IDs.
arrow_right_alt
Handling both positive and negative frequency changes in other collection types.
arrow_right_alt
Optimizing for time complexity while tracking multiple frequent items at once.

help

常见问题

外企场景

继续练习

#3507 移除最小数对使数组有序 I #3510 移除最小数对使数组有序 II #3607 电网维护