最高频率的 ID

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

难度: Medium

你需要在一个集合里动态记录 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 <= 105
  • 1 <= nums[i] <= 105
  • -105 <= freq[i] <= 105
  • freq[i] != 0
  • 输入保证任何操作后，集合中的元素出现次数不会为负数。

Submission

运行时间: 244 ms

内存: 37.0 MB

class Solution:
    def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]:
        ans = []
        n = max(nums)
        id = [0] * n
        mx = 0
        mx_idx = 0
        for i,j in zip(nums,freq):
            id[i-1] += j
            if id[i-1] > mx:
                mx = id[i-1]
                mx_idx = i-1
            elif id[i-1] < mx and (i-1) == mx_idx:
                mx = max(id)
                mx_idx = id.index(mx)
            ans.append(mx)
        return ans

Explain

该题解采用了一个数组 id 来记录每个 ID 的出现频率。数组的索引对应 ID-1（因为 ID 从 1 开始，而索引从 0 开始）。遍历 nums 和 freq 数组，根据 freq 的值来增加或减少 id 数组对应索引的值。同时，使用 mx 来维护当前最高频率的数值，使用 mx_idx 来维护达到最高频率的 ID 的索引。在每次更新 id 数组后，需要检查是否需要更新 mx 和 mx_idx：如果当前 ID 的频率超过了 mx，更新 mx 和 mx_idx；如果当前 ID 是之前的最高频率 ID 但其频率降低了，则需要重新遍历 id 数组以找到新的最高频率和对应的 ID。最后，将 mx 的值添加到结果列表 ans 中。

时间复杂度: O(n*m)

空间复杂度: O(n)

# 定义 Solution 类

class Solution:
    def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]:
        ans = []  # 结果数组
        n = max(nums)  # 计算 nums 中的最大值
        id = [0] * n  # 初始化频率数组
        mx = 0  # 当前最大频率
        mx_idx = 0  # 当前最大频率的索引
        for i, j in zip(nums, freq):  # 遍历 nums 和 freq
            id[i-1] += j  # 更新频率
            if id[i-1] > mx:  # 如果当前 ID 的频率超过了之前的最大值
                mx = id[i-1]  # 更新最大频率
                mx_idx = i-1  # 更新最大频率的索引
            elif id[i-1] < mx and (i-1) == mx_idx:  # 如果当前最大频率 ID 的频率减少
                mx = max(id)  # 重新计算最大频率
                mx_idx = id.index(mx)  # 重新计算最大频率的索引
            ans.append(mx)  # 将当前最大频率添加到结果数组
        return ans  # 返回结果数组

Explore

题解中的逻辑处理确实没有明确指定如何处理多个 ID 频率相同且为最高频率的情况。通常，更新策略可能依赖于具体的应用需求。在题解的当前实现中，如果有多个 ID 的频率相同并且都是最高的，`mx_idx` 将更新为最先达到该频率的 ID 的索引。这是因为每次只在当前 ID 的频率超过现有的最大频率`mx`时更新`mx_idx`。如果需要考虑所有具有最高频率的 ID，可能需要额外的数据结构（如列表）来存储所有这些 ID，并在每次更新时维护此列表。

题解中确实没有明确考虑这种情况。题解所述的逻辑仅在当前最高频率的 ID 频率减少时重新计算最大频率。如果其他 ID 的频率由于某个操作而增加并超过当前最高频率，但不影响当前最高频率 ID 的频率，题解的逻辑不会更新最大频率。这可能导致算法无法正确反映实时的最高频率 ID。要完全准确地处理所有情况，每次频率更新后可能需要重新扫描整个频率数组以确认当前的最高频率，这会增加算法的时间复杂度。

题解中没有明确提到对频率可能变为负数的处理策略。在实践中，频率变为负数通常意味着输入数据有误或者处理逻辑有问题，因为 ID 的出现次数不可能是负数。一个合理的做法是在更新频率前先检查`freq`中的值是否会导致频率数组`id`中的值变为负，如果是，则应该抛出错误或进行某种形式的异常处理。这需要在实现中添加对应的错误检查和处理逻辑，以确保数据的准确性和算法的健壮性。