Easy

题目描述

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

统计在 nums 中每个 target 在 key 后面出现的次数。换句话说，统计满足以下条件的下标 i 的数目：

  • 0 <= i <= nums.length - 2
  • nums[i] == key 且
  • nums[i + 1] == 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
  • 答案是唯一的。

解题思路

这是一道简单的数组遍历和计数问题，可以通过哈希表来高效解决。

解题思路

  1. 遍历数组：从第一个元素开始遍历到倒数第二个元素（因为需要检查当前元素的下一个元素）

  2. 查找匹配：当发现 nums[i] == key 时，记录紧跟其后的元素 nums[i+1]

  3. 频次统计：使用哈希表记录每个跟在 key 后面的数字出现的次数

  4. 找出最大值：遍历哈希表，找到出现次数最多的数字

算法实现

可以使用一次遍历 + 哈希表的方法，时间复杂度为 O(n)，空间复杂度为 O(k)，其中 k 是跟在 key 后面的不同数字的个数。

由于题目保证答案唯一，我们可以在遍历过程中同时维护当前的最大计数和对应的目标值，这样只需要一次遍历就能得到结果。

代码实现

class Solution {
public:
    int mostFrequent(vector<int>& nums, int key) {
        unordered_map<int, int> count;
        int maxCount = 0;
        int result = 0;
        
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums[i] == key) {
                int target = nums[i + 1];
                count[target]++;
                if (count[target] > maxCount) {
                    maxCount = count[target];
                    result = target;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def mostFrequent(self, nums: List[int], key: int) -> int:
        count = {}
        max_count = 0
        result = 0
        
        for i in range(len(nums) - 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

public class Solution {
    public int MostFrequent(int[] nums, int key) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        int maxCount = 0;
        int result = 0;
        
        for (int i = 0; i < nums.Length - 1; i++) {
            if (nums[i] == key) {
                int target = nums[i + 1];
                if (count.ContainsKey(target)) {
                    count[target]++;
                } else {
                    count[target] = 1;
                }
                
                if (count[target] > maxCount) {
                    maxCount = count[target];
                    result = target;
                }
            }
        }
        
        return result;
    }
}

var mostFrequent = function(nums, key) {
    const count = new Map();
    let maxCount = 0;
    let result = 0;
    
    for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历整个数组一次，n 为数组长度
空间复杂度O(k)k 是跟在 key 后面的不同数字的个数，最坏情况下为 O(n)

相关题目