数组中紧跟 key 之后出现最频繁的数字

标签: 数组 哈希表 计数

难度: Easy

给你一个下标从 0 开始的整数数组 nums ，同时给你一个整数 key ，它在 nums 出现过。

统计 在 nums 数组中紧跟着 key 后面出现的不同整数 target 的出现次数。换言之，target 的出现次数为满足以下条件的 i 的数目：

  • 0 <= i <= n - 2
  • nums[i] == key 且
  • nums[i + 1] == target 。

请你返回出现 最多 次数的 target 。测试数据保证出现次数最多的 target 是唯一的。

示例 1：

输入：nums = [1,100,200,1,100], key = 1
输出：100
解释：对于 target = 100 ，在下标 1 和 4 处出现过 2 次，且都紧跟着 key 。
没有其他整数在 key 后面紧跟着出现，所以我们返回 100 。

示例 2：

输入：nums = [2,2,2,2,3], key = 2
输出：2
解释：对于 target = 2 ，在下标 1 ，2 和 3 处出现过 3 次，且都紧跟着 key 。
对于 target = 3 ，在下标 4 出出现过 1 次，且紧跟着 key 。
target = 2 是紧跟着 key 之后出现次数最多的数字，所以我们返回 2 。

提示：

  • 2 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • 测试数据保证答案是唯一的。

Submission

运行时间: 24 ms

内存: 16.3 MB

from typing import List

class Solution:
    def mostFrequent(self, nums: List[int], key: int) -> int:
        count = {}
        max_count = 0
        result = None
        
        n = len(nums)
        for i in range(n - 1):
            if nums[i] == key:
                target = nums[i + 1]
                count[target] = count.get(target, 0) + 1
                if count[target] > max_count:
                    max_count = count[target]
                    result = target
        
        return result

solution = Solution()
nums = [1, 100, 200, 1, 100]
key = 1
print(solution.mostFrequent(nums, key))  # 输出: 100

nums = [2, 2, 2, 2, 3]
key = 2
print(solution.mostFrequent(nums, key))  # 输出: 2

Explain

这个解法使用了一个字典来记录每个可能的target（即紧跟在key后面的数字）的出现次数。遍历数组时，每当发现一个元素等于key时，就查看它后面的元素（target），并在字典中更新该target的计数。同时，我们持续跟踪最大出现次数及对应的数字，如果当前target的计数超过了之前的最大计数，就更新最大计数和结果变量。这种方法确保了我们在一次遍历中即可找到答案。

时间复杂度: O(n)

空间复杂度: O(n)

from typing import List

class Solution:
    def mostFrequent(self, nums: List[int], key: int) -> int:
        count = {}  # 字典用来记录每个target的出现次数
        max_count = 0  # 最大的出现次数
        result = None  # 出现次数最多的target
        
        n = len(nums)
        for i in range(n - 1):  # 遍历数组但停止在倒数第二个元素
            if nums[i] == key:  # 当找到key时
                target = nums[i + 1]  # 获取紧跟key后的元素作为target
                count[target] = count.get(target, 0) + 1  # 更新target的计数
                if count[target] > max_count:  # 如果当前target的计数超过了之前的最大计数
                    max_count = count[target]  # 更新最大计数
                    result = target  # 更新结果为当前的target
        
        return result  # 返回出现次数最多的target

solution = Solution()
nums = [1, 100, 200, 1, 100]
key = 1
print(solution.mostFrequent(nums, key))  # 输出: 100

nums = [2, 2, 2, 2, 3]
key = 2
print(solution.mostFrequent(nums, key))  # 输出: 2

Explore

在这种情况下，当数组只包含一个`key`或者在`key`之后没有其他元素时，后续的代码将无法找到有效的`target`，因为`target`是`key`后面的元素。如果代码尝试访问不存在的`target`（例如数组只有一个元素或`key`是数组的最后一个元素），则不会有任何`target`被添加到字典中。程序在结束遍历后，会检查`result`变量，如果`result`仍然是`None`，则意味着没有找到有效的`target`。这种情况下，函数可以返回`None`或者一个特定的错误值或提示信息，表示无法找到符合条件的`target`。

使用字典（哈希表）来记录`target`的出现次数是因为字典提供了快速的查找、插入和更新操作，这些操作的平均时间复杂度是O(1)。与之相比，如果使用数组或计数排序，我们可能需要事先知道`target`可能的范围（例如最大值和最小值），以便分配足够的空间进行计数，这在不知道`target`范围的情况下是不可行的。此外，如果`target`的值域非常大，但实际出现的`target`种类较少，则使用数组会导致大量空间浪费。因此，字典在这种情况下是更灵活和空间效率更高的选择。

在遍历数组时，代码通过只遍历到数组的倒数第二个元素（即使用`for i in range(n - 1)`）来确保不会遇到数组越界的问题。这种遍历方式保证了当我们在代码中引用`nums[i + 1]`时，`i + 1`总是一个有效的索引。如果`i`等于`n-1`（数组的最后一个索引），则`i + 1`会超出数组界限，但由于循环的限制，这种情况不会发生。

当`key`连续出现时，例如在数组`[key, key, target]`中，每个`key`后面的元素都被视为`target`。在这个例子中，第一个`key`后面直接是另一个`key`，所以第二个`key`也被计为一个`target`。随后，第二个`key`后面是`target`，这个`target`也会被计入统计中。因此，这种情况下的输出会包括所有紧跟在`key`后面的元素的统计，但不会对结果的正确性产生影响。只要逻辑正确地处理每一个`key`后面的元素，即使`key`连续出现也能正确统计每个`target`的出现次数。